|
ru.perl
- RU.PERL ----------------------------------------------------------------------
From : Yuriy Kaminskiy 2:5020/517.21 24 Dec 2000 03:22:50
To : Tarasov Sergej
Subject : Re: сортировка большого хеша
--------------------------------------------------------------------------------
>>>>> On 18:08 22/12/2000, tarasov@pmi.lv writes:
TS> проблеме. Сортировка слиянием - это уже крайний случай, слишком
TS> медленно.
Серьезно? Сортировка слиянием - это O(n*log n).
То бишь - вполне приемлемая скорость. Особенно, если достаточно мелкие
(<free_physical_ram) фрагменты сортировать при помощи sort.
Кстати, как я понял из man perlfunc, sort пользуется qsort(3) [в
исходники смотреть влом, тем более, что в разных версиях это могли
десять раз поменять]. А он в каких-то версиях glibc, AFAIR, был
реализован через сортировку слиянием, а не быструю сортировку :)))
TS> есть хеш key1 -> val1; key2 -> val2 и т.д. Если не хватает памяти
TS> одновременно иметь и хеш и массив, который сортируется, нужно
TS> избавиться от хеша. Hапример вытаскивать по одной паре значений из
TS> хеша, добавлять их в массив и удалять этот ключ из хеша. В итоге
... мы не^&* не получим. Потому что при удалении элементов из хеша его
реальный размер не уменьшается. Плюс фрагментация памяти. И т.д.
TS> Hаверняка будет быстрее, чем сортировка слиянием.
Hу-ну.
--
Yuriy Kaminskiy.
--- Gnus v5.2.25/XEmacs 19.14
* Origin: Kyle Katan's station (2:5020/517.21@fidonet)
Вернуться к списку тем, сортированных по: возрастание даты уменьшение даты тема автор
|
