Erste Ziffer einer Zahl

[Ceka]

Hallo,

ich möchte von z. B. 123 die erste Ziffer bekommen also 1.
Ich möchte es aber in konstanter Zeit und die Zahl kann beliebig groß werden, ich habe es bereits folgendermaßen versucht:

(123 / 100) % 10
Wird die Zahl jedoch größer funktioniert dies logischerweise nicht mehr.
Kann mir jemand weiterhelfen?

Danke =)

 

[Robat]

Du könntest die Zahl in einen String wandeln und mit charAt(0) arbeiten. Gibt aber sicherlich auch noch schönere Wege.

 

[Ceka]

Okay, Danke.
Was macht Java intern, wenn ich einen Integer in einen String umwandel?
Geht das in konstanter Zeit?

 

[Meeresgott]

int i = 123;
String s = Integer.valueOf(i);
char   c = s.charAt(0);
i = Character.getNumericValue(c);

und das machst du einfach 1000 mal und stoppst die Zeit, dann weißt du es

 

[JStein52]

dann weißt du es

was weiss er dann

 

[Ceka]

Habe gerade bemerkt, dass das doch keine so Gute Idee ist bzw. nicht funktioniert.
Ich habe folgendes vor:
Ich habe z. B. 123 und möchte jetzt daraus 230 berechnen.

Bei 123 würde man das folgendermaßen machen:
(123 - (1*100)) * 10
Ich weiß jetzt nur nicht, wie ich das machen soll, wenn ich nicht weiß wie groß die Zahl ist.
Ich könnte es zwar so machen, indem ich die Zahl in ein String caste und somit die länge und die erste Ziffer bekommen würde.
Aber gibt es nicht eine elegantere Lösung?

 

[JStein52]

Was willst du eigentlich genau machen ? Auf die erste Ziffer einer Zahl 1 draufaddieren ?

Edit: nee war Quatsch. Du willst die Ziffern um eine Stelle nach links schieben und rechts mit 0 auffüllen ??

 

[Ceka]

Ich habe z. B. 123 und möchte jetzt daraus 230 berechnen.
s. 6. Beitrag

 

[Meniskusschaden]

Ehrlich gesagt kann ich bei dieser Aufgabe noch nicht allzu viel mit den Anforderungen "in konstanter Zeit" und "beliebig groß" anfangen. Was ist denn der Datentyp der Zahl?

 

[Ceka]

ein int und die Zahl kann 123 sein aber auch 1123 und ich möchte folgendes:
bei 123:
230
bei 1123:
1230

 

[DrZoidberg]

Das könntest du z.B. so machen

int z = 1123;
int z2 = 0;
int m = 10;

while(z > 9) {
  z2 += z%10 * m;
  m *= 10;
  z /= 10;
}

 

[Ceka]

Die Laufzeit sollte konstant sein, also die Laufzeit sollte nicht in Abhängigkeit der Länge der Zahl sein o. ä..

 

[DrZoidberg]

Das ist nicht möglich. Wenn du mit Zahlen im Hexadezimalsystem arbeiten würdest ginge es, aber nicht im Dezimalsystem.
Es sei denn du erstellst eine gigantische Lookup Tabelle mit über 4 Milliarden Einträgen. Das wäre aber sehr unpraktisch.

 

[Meniskusschaden]

Die Laufzeit sollte konstant sein, also die Laufzeit sollte nicht in Abhängigkeit der Länge der Zahl sein o. ä..

Meinst du jetzt "konstant" im Sinne von O(1)? Das müsste die Lösung von @DrZoidberg doch erfüllen, weil die Zahl ja höchstens Integer.MAX_VALUE groß sein kann. Es gibt also eine feste Obergrenze für die Anzahl an Iterationen.
Oder meinst du "konstant" im Sinne von "immer exakt gleich lang"? Dann könntest du eine ausreichend große Zeitspanne festlegen. Dann misst du in deinem Programm die Zeit für die Berechnung und wartest die verbleibende Zeit einfach ab.
Oder geht es dir nur um eine geschlossene Formel? Dann könntest du es z.B. so machen:

public static int shiftLeft(int x) {
    int y = (int)Math.pow(10, (int)Math.log10(x));
    return (x-(x/y)*y)*10;
}

Aber die Berechnungen werden für unterschiedliche Zahlen vermutlich auch nicht exakt gleich lange dauern. In der Praxis würde ich deshalb auch eine schlichte Schleife bevorzugen.

 

[Ceka]

Okay, vielen Dank erstmal, ich werde mal schauen =)

 

[Xyz1]

Das könntest du z.B. so machen

Das ist mindestens doppelt so schnell, wie das mit toString().

Ich stelle beide Methoden einmal vor:

    static int lastDi1(int i) {
        String string = Integer.toString(i);
        if (string.charAt(0) != '-') {
            return string.charAt(0) - '0';
        } else {
            return -string.charAt(1) + '0';
        }
    }

    static int lastDi2(int i) {
        while (i < -9 || i > 9) {
            i /= 10;
        }
        return i;
    }

Zu testen:

        for (int j = -98; j < 99; j++) {
            System.out.println(lastDi1(j) + "  " + lastDi2(j));
        }

Warum ist der Drei- bis Vierzeiler mindestens doppelt so schnell?
Dazu habe ich mal einen kleinen Benchmark geschrieben, der sogar etwas ungenau sein könnte:

        ArrayList<Integer> list = new ArrayList<>(11_000_000);
        Random r = new Random(0);
        long t1 = System.currentTimeMillis();
        for (int j = 0; j < 10_000_000; j++) {
            int i = r.nextInt();
            int k = lastDi1(i);
            list.add(k);
        }
        long t2 = System.currentTimeMillis();
        System.out.println(list.get(0) + "  " + list.get(5_000_000) + "  " + list.get(9_999_999));
        list.clear();
        long t3 = System.currentTimeMillis();
        for (int j = 0; j < 10_000_000; j++) {
            int i = r.nextInt();
            int k = lastDi2(i);
            list.add(k);
        }
        long t4 = System.currentTimeMillis();
        System.out.println(list.get(0) + "  " + list.get(5_000_000) + "  " + list.get(9_999_999));
        System.out.println(t2 - t1);
        System.out.println(t4 - t3);
        System.out.println((t4 - t3) * 100d / (t2 - t1));

-1  9  6
5  -1  -2
813
391
48.09

(Im 2. Durchlauf sind es nur noch 40%.)

Und jetzt mal was Praktisches: Geht man von int aus, beträgt die Geschwindigkeit O(32) bzw. O(31)... Theoretisch beträgt die Geschwindigkeit O(n). Das kann auch nicht umgangen werden.

----
So , und nun möchte ich wissen, wie diese Aufgabe mit dem Shiften gemeint war? Simples Shiften und 0 anfügen ist es ja nicht. :/

 

[Ceka]

Okay, vielen Dank =)

 

[kodela]

Warum beschreibst Du Dein Problem nicht abstrakt? Eine solche abstrakte Beschreibung kann man natürlich anhand von Beispielen anschaulicher machen. Du zeigst aber nur Beispiele und verwendest Formulierungen, unter denen man sich alles Mögliche vorstellen kann.

Ich weiß nicht, ob ich Dein Problem damit treffe, ich will es einmal versuchen:

"Von einer positiven Integerzahl soll die erste Dezimalstelle entfernt und zur Erhaltung der Stellenzahl am Ende eine Null hinzugefügt werden. Diese Umwandlung sollte für alle Zahlen, unabhängig von ihrer Größe, in gleichbleibender Zeit erfolgen. Aus "123" sollte also zum Beispiel "230" oder aus "7613" sollte "6130" werden."

Das würde so ungefähr dem entsprechen, was Du zuletzt geschrieben hast, passt aber überhaupt nicht mit dem zusammen, was Du im ersten Beitrag wolltest:

ich möchte von z. B. 123 die erste Ziffer bekommen also 1.

Die erste Stelle willst Du ja nach Deinen späteren Ausführungen verwerfen.

Damit man Dein Problem nachvollziehen kann, solltest Du auch in kurzer Form beschreiben, warum Du was machen willst und warum eine Umwandlung immer in der selben Zeit erfolgen soll, auch ob du bedacht hast, dass die Zeitunterschiede für eine solche Umwandlung, egal wie sie nun ausgeführt wird, im Bereich von millionstel Sekunden liegen.

 

[JStein52]

Hab ich doch oben schon gesagt: er schiebt alle Ziffern eins nach links, ganz links die fällt raus und rechts wird eine 0 aufgefüllt.

 

[kodela]

Und warum schreibt er dann:

ich möchte von z. B. 123 die erste Ziffer bekommen also 1.

Es wäre doch schön, wenn er sich mindestens so viel Mühe mit der Darstellung seines Problem machen würde, wie diejenigen, die ihm helfen wollen.

 

[kodela]

Ich habe mir einmal die Mühe gemacht, die beiden nach meiner Meinung besten Lösungsvorschläge miteinander zu vergleichen.

Mit dem Vorschlag von @DrZoidberg werden bei mir für eine Million Konvertierungen einer dreistelligen Zahl 11,0 millionstel Sekunden benötigt. Mit einer sechstelligen Zahl verdoppelt sich die Zeit auf 22,0 millionstel Sekunden.

Bei dem selben Test nach dem Vorschlag von @Meniskusschaden ist das Ergebnis mit 9,5 millionstel Sekunden einen Tick besser. Mit einer sechsstelligen Zahl wird der Vorsprung größer. hier werden nur 15,0 millionstel Sekunden benötigt.

 

[JStein52]

Womit schon mal beide Vorschläge rausfallen.

 

[Meniskusschaden]

Womit schon mal beide Vorschläge rausfallen.

Das stimmt, wobei ich immer noch Zweifel habe, wie der Begriff "konstante Zeit" hier gemeint ist. Wegen der Größenbeschränkung ist O(1) ja sowieso gegeben und exakt gleich lang dauernde Berechnungen erscheinen mir sinnlos. Ich würde die Berechnungen je nach Anforderung so schnell oder einfach wie möglich bzw. nötig machen und falls ein fester Takt benötigt wird, einen eigenen Taktgeber bereiststellen, der sich darum kümmert.

Und warum schreibt er dann:

ich möchte von z. B. 123 die erste Ziffer bekommen also 1.

Er hat sich ja in Post #6 selbst überlegt, dass er es anders machen wollte, als zunächst geplant. Ich stimme dir aber zu, dass die Beschreibungen nicht so gut waren. Ich mußte auch erst einmal überlegen, was er überhaupt meint.

 

[JStein52]

Ich glaube es geht ihm bei dieser Aufgabe nicht darum dass ihm etwas zu langsam oder zu schnell ist sondern es ist eine mehr akademische Aufgabenstellung einen Algorithmus zu finden der in konstanter Zeit arbeitet. Es geht nicht um 10 msec. hin oder her

 

[kodela]

Wenn es primär um die konstante Zeit ginge, dann muss er es über die Stringkonvertierung realisieren. Hier eine Lösungsmöglichkeit, die zwar um den Faktor 10 langsamer ist, als die beiden von mir getesteten, dafür aber, was die Zeit anbelangt, ziemlich konstant ist:

     static int stringKonvert(int n) {
        String sn = String.valueOf(n);
        return Integer.parseInt(sn.substring(1) + "0");
    }

Womit schon mal beide Vorschläge rausfallen.

Kannst Du mir das "Warum" bitte erklären?

@Meniskusschaden:
Kannst Du mich aufklären, was mit O(n) - oder ähnlich, gemeint ist?

 

[JStein52]

dass muss er es über die Strinkonvertierung realisieren

Woher nimmst du den Mut zu denken valueOf und parseInt seien unabhängig von der Anzahl Stellen der Zahl "n"

Und das "warum" ist ganz einfach, du hast es ja selbst gemessen, beide Varianten waren abhängig von der Anzahl Stellen der Zahl und eben nicht in "konstanter Zeit"

 

[JStein52]

Wegen der Größenbeschränkung ist O(1) ja sowieso gegeben

Ich habe deine Argumentation oben zu diesem Thema eh nicht ganz verstanden. Nur weil ein Integer z.B. in Java eine bestimmte Obergrenze hat heisst das doch nicht dass der Algorithmus unabhängig von der Anzahl der Stellen der Zahl ist ??? Oder was sagt der theoretische Informatiker zu dem Thema ?

 

[Xyz1]

Oder was sagt der theoretische Informatiker zu dem Thema ?

Der Techniker würde jetzt sagen, wir müssen bei Dualrechnersystemen, Oktalrechnersystemen, Dezimalrechnersystemen und Quantenrechner anfangen. (Oder halt Turingmaschinen) Und dann mit der Mathematik weitermachen.

Schade, dass meines nicht zur Disposition stand. Aber ich habe das Muster der nachfolgenden Aufgabenstellung noch nicht ganz verstanden. (Deswegen frage ich so blöde nach) Wievielstellig können die Zahlen sein - und wivielstellig sollen sie werden? Was soll mit allen Ziffern (außer der ersten) passieren, was soll für die 0te Ziffer?

@kodela : Das ist eine unter Informatikern gebräuchliche Notation - und wenn man sie schreibt, wissen alle Bescheid.

 

[JStein52]

Wievielstellig können die Zahlen sein - und wivielstellig sollen sie werden?

Sie können n-stellig sein und sie bleiben es auch. 1234 -> 2340 oder 987654321 -> 876543210 usw.

 

[Xyz1]

Mist das alles... Gleich wieder vergessen.

(DAS KOMMT DAVON; WENN MAN DIE AUFGABENSTELLUNG NICHT VERSTEHT)

 

[Meniskusschaden]

@Meniskusschaden:
Kannst Du mich aufklären, was mit O(n) - oder ähnlich, gemeint ist?

Ich hoffe, mein Erklärungsversuch ist nicht zu unwissenschaftlich (eine korrekte Darstellung gibt es bei Wikipedia): Mit der O-Notation teilt man die Laufzeit von Algorithmen in Klassen ein. Jede Klasse wird durch eine Funktion g definiert und eine Funktion f gehört dieser Klasse an, wenn f höchstens um einen konstanten Faktor langsamer ist, als g.
Ich denke das hat den Sinn, dass ein schnellerer Rechner auch nur um einen konstanten Faktor schneller als ein langsamerer Rechner ist, so dass ein asymptotisch besserer Algorithmus einen asymptotisch schlechteren bei hinreichend großer Eingabemenge schlägt, egal wieviel langsamer sein Rechner ist.

Ich habe deine Argumentation oben zu diesem Thema eh nicht ganz verstanden. Nur weil ein Integer z.B. in Java eine bestimmte Obergrenze hat heisst das doch nicht dass der Algorithmus unabhängig von der Anzahl der Stellen der Zahl ist ???

Nein, unabhängig ist es nicht. Ich meine es so, dass der schlechtere Algorithmus je nach Eingabe vielleicht mal doppelte Laufzeit hat, mal dreifache, aber eben höchstens z.B. zehnfache Laufzeit, weil die Eingabe nicht so groß werden kann, dass er z.B. 20 mal, 30 mal, 40mal ... schlechter wird. Mag aber sein, dass das für den theoretischen Informatiker nicht präzise genug oder sogar falsch ist.

EDIT: Oder weniger kompliziert ausgedrückt: Wenn ich höchstens zehn Schleifen-Iterationen habe bis ich fertig bin, ist das eben O(10) und das ist O(1).

 

[mrBrown]

Nein, unabhängig ist es nicht. Ich meine es so, dass der schlechtere Algorithmus je nach Eingabe vielleicht mal doppelte Laufzeit hat, mal dreifache, aber eben höchstens z.B. zehnfache Laufzeit, weil die Eingabe nicht so groß werden kann, dass er z.B. 20 mal, 30 mal, 40mal ... schlechter wird. Mag aber sein, dass das für den theoretischen Informatiker nicht präzise genug oder sogar falsch ist.

EDIT: Oder weniger kompliziert ausgedrückt: Wenn ich höchstens zehn Schleifen-Iterationen habe bis ich fertig bin, ist das eben O(10) und das ist O(1).

Ich bin mir nicht sicher, Ob O-Notation hier passend ist - die Eingabe ist schließlich bei ints mit 32 ziemlich begrenzt, und der Grenzwert mit n->unendlich kaum sinnvoll möglich.
Bei unendlich großen Zahlen landet man je nach Speicherung bei O(1) oder O(n)

 

[JStein52]

Wenn ich höchstens zehn Schleifen-Iterationen habe bis ich fertig bin, ist das eben O(10) und das ist O(1)

Das schon. Hat man aber beim vorliegenden Problem doch gar nicht. Ein Algorithmus ist doch zunächst einmal unabhängig von einer Programmiersprache.

 

[JStein52]

Bei unendlich großen Zahlen landet man je nach Speicherung bei O(1) oder O(n)

Wie meinst du das mit der Speicherung ?

 

[Meniskusschaden]

Ein Algorithmus ist doch zunächst einmal unabhängig von einer Programmiersprache.

Ja. Deswegen hatte ich in Post #9 nach dem Datentypen gefragt. Wenn man unabhängig wäre, könnte man sich ja einen eigenen Typen ausdenken, der diese Operation in O(1) unterstützt. Es ging aber konkret um integer, deshalb bin ich davon ausgegangen, dass wir hier nicht mehr neutral unterwegs sind.

 

[Meniskusschaden]

Ich bin mir nicht sicher, Ob O-Notation hier passend ist

Das sehe ich auch so. Deshalb hätte ich gerne konkreter gewusst, was er hier wirklich mit "konstant" meint.

 

[mrBrown]

Wie meinst du das mit der Speicherung ?

Welche Codierung für die Zahl und wie die gespeichert ist, binär und feste Größe ist nicht das einzige.

BCD mit Variabler Größe zB wäre O(1), da ist die erste Ziffer einfach nur der erste oder zweite Halbbyte.
Bei beliebig größer Binärzahl ists eher O(N)

 

[JStein52]

BCD mit Variabler Größe zB wäre O(1), da ist die erste Ziffer einfach nur der erste oder zweite Halbbyte.

Aber wie du es drehst und wendest, du musste doch auch da jede Ziffer um eins nach links verschieben oder nicht

 

[mrBrown]

Aber wie du es drehst und wendest, du musste doch auch da jede Ziffer um eins nach links verschieben oder nicht

Wenn man das als Array von Halbbytes betrachtet, muss man den Pointer auf das erste Element nur um eins erhöhen (bzw das erste Halbbyte nullen) und am anderem Ende eins dran hängen

 

[Xyz1]

Hat schon jemand:

    static int schiebeRum(int i) {
        return i % (int) Math.pow(10, Math.floor(Math.log10(i) )) * 10;
    }

gemacht?

Ist euch nebenbei aufgefallen, dass aus 1234 2340 wird zwar, aber aus zB 101 10 wird???

Nichts was nicht schon einmal diskutiert wurde: https://stackoverflow.com/a/2051880

However, funktioniert "toll" für positive Zahlen bis 100,000,000.

Aber wie schnell ist es? Es mag harmlos aussehen, es ist aber unter den schnelleren Lösungen die langsamste, unter den besten die schlechteste, und hat wegen log und pow IN DER THEORIE auch keine konstante Laufzeit.

Alles "toll"?

 

[kodela]

Um was geht es hier eigentlich noch. Da braucht nur einer eine unausgegorene Frage zu stellen, schon springt die Meute darauf los und vergisst völlig, dass die Frage im Unterforum "Java Basics - Anfänger-Themen" gestellt wurde. Es ist auch nicht mehr wichtig, um was genau es geht, wird die erste Ziffer einer Zahl gesucht oder soll diese nur entfernt und dann am Ende durch eine Null die Anzahl der Ziffern durch Hinzufügen einer Null korrigiert werden.

Man wartet auch nicht ab, bis der Fragesteller sein Problem so dargestellt hat, dass man damit etwas anfangen kann, neun man "verlustiert" sich an dem gefundenen "Fressen", wirft mit Fachchinesisch nur so um sich, selbst weiß man ja, was man damit meint und der Anfänger - ach ja, der Anfänger, - so wichtig es der ja auch nicht.

Denkt einmal darüber nach.

 

[Meniskusschaden]

Ehrlich gesagt verstehe ich nicht, was du meinst. Die Dinge die du kritisierst sind in diesem Thread doch gar nicht geschehen. Es gab konstruktive Vorschläge und Erklärungsversuche. Es gab zwei unklare Aufgabenstellungen und deshalb Rückfragen und Interpretationsversuche, um trotzdem eine Lösung im vermuteten Sinn des Aufgabenstellers zu finden. Es gab wenig Feedback vom Aufgabensteller. Worauf hätte man noch warten sollen? Sein Problem scheint gelöst zu sein. Warum soll man da nicht weiter diskutieren, wenn es in dem Kontext noch etwas zu bequatschen gibt?

 

[JStein52]

Um was geht es hier eigentlich noch. Da braucht nur einer eine unausgegorene Frage zu stellen, schon springt die Meute darauf los

Dies ist doch ein Diskussionsforum oder nicht ? Selbst wenn der Fragensteller sich nicht mehr beteiligt darf doch weiter diskutiert werden. Es wurde weder unsachlich diskutiert noch wurde jemand daran gehindert sich ebenfalls zu beteiligen.

 

[kodela]

Dies ist doch ein Diskussionsforum oder nicht ? Selbst wenn der Fragensteller sich nicht mehr beteiligt darf doch weiter diskutiert werden. Es wurde weder unsachlich diskutiert noch wurde jemand daran gehindert sich ebenfalls zu beteiligen.

Ja, das ist ohne Zweifel alles richtig. Ich habe mich ja selbst auch an dieser Diskussion beteiligt. Zum Schluss habe ich mich allerdings gefragt, was diese Diskussion dem Fragesteller bringt, ob irgend jemand aus dieser Diskussionsrunde sein Problem noch im Auge hat. Vor lauter Freude an der Diskussion haben wir sogar selbst in Kauf genommen, die Diskussion zu führen, ohne uns so recht einig zu sein, um was genau wir diskutieren, darüber, wie man die erste Ziffer einer Zahl feststellt, oder, wie man die erste Ziffer ein Zahl entfernt und das Ergebnis mit 10 multipliziert.

Das eine ist zwar im vermuteten Sinne des Fragestellers möglich, das andere jedoch nur dann, wenn der Fragesteller ausschließlich mit Strings arbeitet und nicht mit Integerwerten. Letztere kennen bekanntlich keine führenden Nullen. Hätte man ihm vielleicht sagen sollen.

 

[JStein52]

ohne uns so recht einig zu sein, um was genau wir diskutieren

Ich fand schon dass wir uns einig waren dass der Hauptknackpunkt die "Anforderung" -in konstanter Zeit- ist. Und darüber ging zum Schluss die Diskussion. Führende Nullen sind da nur pillepalle

 

[Xyz1]

@DrZoidberg hatte als erstes die Kanonen aufgefahren... Dann darf ich auch ein bisschen Rumballern...

Falls -konstante Zeit- noch offen ist, dann ist es wichtig, auf was sich das bezieht...

https://stackoverflow.com/a/34247224

For numbers that have limited bit-ness (like float/double/int) you can consider these functions (along with other once like sin/cos) as O(1) since there is well defined bound for them when they exectured by floating-point processor,[...]

For arbitrary long numbers you'd have to use significantly more complicated estimates which also will have to be directly tied to implementation you have.[...]

Bei uns können wir beides annehmen, O(1) und O(n)... nur wichtig, wie man das begründet.

Wenn @kodela regelmäßig mit einem rosa Elepfanten mit Ohren als Propeller durch die Gegend fliegt... dann ist das eben so.

 

[JStein52]

hatte als erstes die Kanonen aufgefahren

Hier hatte doch gar keiner Kanonen aufgefahren ...