array_slice mit grossen Arrays

[misstvielmisst]

Hallo,

ich hatte gerade eine Anwendung bei der aus einem
ca. 100.000 integer Werte umfassendes Array
ca. 30.000 mal jeweils eine kurze Sequenz (1-2 Elemente) ausgeschnitten
werden musste.
Dabei ist mir leider unangenehm aufgefallen das "array_slice" gut
80x langsamer als eine "while() kopie[] = array[index]" ist.
Bei sehr grossen Arrays und sehr kleinen Ausschnitten und
vielen Wiederholungen kann diese Funktion auch mal
mehrere hundertmal langsamer sein!

Ich finde das recht erstaunlich und kann mir das kaum erklären,
ausser mit sehr ungeschicktem CopyOnWrite.

Über den Daumen gepeilte Empfehlung:
if count(array) > count(ausschnitt) * 50 * durchläufe
then loop
else array_slice

[Beat]

ich hatte gerade eine Anwendung bei der aus einem
ca. 100.000 integer Werte umfassendes Array
ca. 30.000 mal jeweils eine kurze Sequenz (1-2 Elemente) ausgeschnitten
werden musste.
Dabei ist mir leider unangenehm aufgefallen das "array_slice" gut
80x langsamer als eine "while() kopie[] = array[index]" ist.
Bei sehr grossen Arrays und sehr kleinen Ausschnitten und
vielen Wiederholungen kann diese Funktion auch mal
mehrere hundertmal langsamer sein!

Das ist bekannt, und meiner Ansicht nach auch logisch. Ich habe zwar von PHP keine Ahnung, aber in Perl gilt das auf jeden Fall.

Ich finde das recht erstaunlich und kann mir das kaum erklären,
ausser mit sehr ungeschicktem CopyOnWrite.

Wenn du aus einem Array 1..1000 das 1. Element mit slice rausschneidest, müssen alle nachfolgenden Indices umgeschrieben werden.
Dieses Umschreiben ist also schon fast so anstrengend wie Kopie in einen anderen Array.
Falls man slice überhaupt anwendet, empfiehlt es sich, den Array von hinten aufzuslicen, mit der Begründung, dass slicen den Array prinzipiell verkürzt.

mfg Beat

[Matti Maekitalo]

Tach auch.

Das ist bekannt, und meiner Ansicht nach auch logisch.

Sehe ich nicht so.
Ein array_slice für ein Element kann bei einer doppelt verketteten Liste durchaus in O(1) implementiert werden (es müssen ja nur die Zeiger beim Vorgänger- und Nachfolge-Element umgebogen werden, das Suchen des richtigen Elements meinetwegen noch in O(n) dazurechnen, wenn man keine Iteratoren nutzt).

Siehe z.B. C++ STL:
"Fill insert, range insert, and range erase are linear.
The complexities of single-element insert and erase are sequence dependent. "

gültig etwa für einen std::vector, was ja mit einem PHP-Array mit Zahlen als Indizes vergleichbar ist.

Wenn du aus einem Array 1..1000 das 1. Element mit slice rausschneidest, müssen alle nachfolgenden Indices umgeschrieben werden.

Wenn man die Verknüpfung Array-Index => Element fest speichert, ist das korrekt.
Dies ist etwa der Fall für einen assoziativen Array (in perl wäre es der Hash).

Nur: wenn man nicht vorhat, nicht-zahlenbasierte Array-Indizes zu verwenden, ist eine feste Speicherung gar nicht notwendig. Den []-operator kann man auch ohne feste Verknüpfung implementierbar.

Bis die Tage,
Matti

[misstvielmisst]

Das ist bekannt, und meiner Ansicht nach auch logisch. Ich habe zwar von PHP keine Ahnung, aber in Perl gilt das auf jeden Fall.

Wenn der array parameter von array_slice eine Referenz wäre, ist er aber nicht. Das übergebene Array muss/darf/kann nicht verändert werden.

array_slice(range(1,1<<24),1<<12,1))

ist daher möglich, die Laufzeit davon allerdings nicht.)