RU/2: Форум. Общение пользователей и разработчиков OS/2 (eCS). : Уже не джаба.


Список сообщений | Написать новое | Ответить на сообщение | Домой Поиск:
Предыдущее сообщение | Следующее сообщение
From : Stalker
To : saa
Subj : Уже не джаба.
> Ага, давай, на чем ты там будешь писать - сравни время выполнения
>
> for (i=0; N>i; i++) a[i]=new int;
> и
> for (i=0; N>i; i++) delete a[i];
>
> где int *a[N];
> а N - не менее 100000

Вот в жабе delete нету :-) А твой пример должен везде работать одинакого, разве что в виртуал паскакле будет по другому - он сам с кучей геморроется (imho).

> > > Я с большим удовольствием почитаю твой исходничек, который с такими строками работает.
>
> Я кстати тоже. Подскажи, где почитать, чтобы узнать алгоритм, быстрый и безразличный к статистике как qsort и нетребовательный к размеру ОЗУ и времени выборки внешней памяти.

Нуууу блин. Если рассмотреть алгоритм qsort-а, то он де факто строит сбалансированное дерево. Однако вместо хранения элементов в памяти он их, мммм, перестанавливает. Соответственно и памяти жрется мало. В случае больших массивов сразу напрашивается вариант строить дерево хеш функций. Это позволит избежать многократного перемещения элементов, повышая за счет этого производительность (ведь основное время тратится именно на выборку и перемещение). За счет построения дерева можно к тому же сократить время работы проги, так как сортировать весь массив не требуется. Причем значительно. Грубо говоря: требуется балансировка не всего дерева, а только одной его ветки. Соответственно и количество сравнений снижается в кубической прогрессии. (На самом деле не совсем конечно). Ну и т.д. Эти и другие более умные вещи можно почитать в книжке Кнутта (по моему так), выпущенной в каком то занюханном 60 году. Вот-с.
Что касается сравнения больших строк, например в 500мег (как тут ехидно заметил товарисч Кулешов), то для этого существует другие алгоритмы - например можно использовать модифицированный(на >,<,=) алгоритм Кнутта-Морриса-Братта, для сравнения двух строк. Есстественно его придется написать на asm-е для повышения производительности. Вот конкретно в этом
месте жаба конкретно и отсосет.

> > Ты отказался сформулировать тестовую задачу, это сделал за тебя я.
>
> Это очень хорошо, что ты её уже сформулировал, только вроде как никто кроме тебя её ещё не понял.

Я её уже повторно сформулировал. Даже товарисч Кулешов её понял :-)

>А ещё ты не сформулировал, на каких примерах сверять будешь.

Нормально написанный софт должен нормально работать на любых примерах.


Mon 03 Dec 2001 18:39 Mozilla/4.61 [en] (OS/2; U) via Smart Cache 0.45



Programmed by Dmitri Maximovich, Dmitry I. Platonoff, Eugen Kuleshov.
25.09.99 (c) 1999, RU/2. All rights reserved.
Rewritten by Dmitry Ban. All rights ignored.