Comments 12
я на флэше не пишу, но мне все же интересно — а часто вам приходится сортировать 75 миллионов элементов в actionscript?
Обожаю хабрастатьи про сортировки, но, извините, я не уследил за ходом Вашей мысли.
Кому именно родная «родная сортировка»? )))
Кому именно родная «родная сортировка»? )))
экземплярам Vector'а(типизированный массив в as3).
new [3, 1, 4, 2, 5].sort(Array.NUMERIC);
короче native sort
new [3, 1, 4, 2, 5].sort(Array.NUMERIC);
короче native sort
Имхо, для того. чтобы читателям статьи было интересно её читать, неплохо было бы указать какой именно алгоритм применяется в этой «native sort».
Во вторых конечно же нужно понимать с какими данными мы работает, что ожидаем ибо существует огромное количество сортировок и каждая дает плюс в своей области.
И имхо в вашем случе было бы проще использовать quicksort, для массивов уж точно. mergeSort для структур даных с послеовательным доступом да и запускать его намного лучше скажем в 2 4 8 и тд потоках когда у вас реально есть 100 миллионов записей и есть 8 ядер процессора, а рузультат нужен вчера и конечно же пропускная способность дисков и памяти позволит нагрузить все 8 ядер.
Во вторых конечно же нужно понимать с какими данными мы работает, что ожидаем ибо существует огромное количество сортировок и каждая дает плюс в своей области.
Родная сортировка требует примерно n*1.5 дополнительной памяти, mergeSort — ровно n.откуда информация, как сравнивали?
И имхо в вашем случе было бы проще использовать quicksort, для массивов уж точно. mergeSort для структур даных с послеовательным доступом да и запускать его намного лучше скажем в 2 4 8 и тд потоках когда у вас реально есть 100 миллионов записей и есть 8 ядер процессора, а рузультат нужен вчера и конечно же пропускная способность дисков и памяти позволит нагрузить все 8 ядер.
память определял на глаз, смотрел сколько плеер съедает памяти.
на 20 миллионов native sort — 246940kb, mergeSort — 168656kb.
168656 / (((20000000*32)/8/1024)*2) = 1.08
246940 / (((20000000*32)/8/1024)*2) = 1.58
случайный массив делается
какой алгоритм в native sort — я хз, не смог найти.
например по ссылке в комменте habrahabr.ru/post/207784/#comment_7154708 — в статье говорят — пузырьком, в комментах — quicksort
на 20 миллионов native sort — 246940kb, mergeSort — 168656kb.
168656 / (((20000000*32)/8/1024)*2) = 1.08
246940 / (((20000000*32)/8/1024)*2) = 1.58
случайный массив делается
result[i] = Math.random() * length + .5 | 0;
какой алгоритм в native sort — я хз, не смог найти.
например по ссылке в комменте habrahabr.ru/post/207784/#comment_7154708 — в статье говорят — пузырьком, в комментах — quicksort
Если хотите извращений, возьмите ещё вот эту штуку да погоняйте someideas.ru/2011/06/11/быстрая-сортировка-на-as-3-0/
А ещё, приведите пожалуйста оригинальный код который вы использовали для вызова родной сортировки. Там тоже фокусы могут быть.
vector.sort() реально тормозной я использовал сортировку Шелла
artman.fi/2009/06/as3-sorting-algorithm-faster-than-native-sorting/
Работает всегда быстрее, на частично отсортированных данных быстрее в разы
Попробую ваш вариант
artman.fi/2009/06/as3-sorting-algorithm-faster-than-native-sorting/
Работает всегда быстрее, на частично отсортированных данных быстрее в разы
Попробую ваш вариант
UFO just landed and posted this here
UFO just landed and posted this here
Sign up to leave a comment.
Merge sort и AS3. Обгоняем родной Vector.sort(Array.NUMERIC)