Библиотека для быстрых операций с массивами

← →
Zenith (2010-09-17 09:35) [0]

Посоветуйте, пожалуйста, библиотеку для очень быстрых операций с одномерными массивами (суммирование элементов, сортировка, поиск и т.д.)

← →
Sha © (2010-09-17 09:48) [1]

Быстрее самому написать.

1. Суммирование - пробежаться по массиву,
в одном цикле сложить отдельно четные и нечетные, потом сложить суммы.
Можно попробовать развернуть цикл не по 2, а по 4.

2. Сортировка - QuickSort.

3, Поиск - двоичный.

← →
Zenith (2010-09-17 09:52) [2]

> 1. Суммирование - пробежаться по массиву,
> в одном цикле сложить отдельно четные и нечетные, потом
> сложить суммы.

Почему это дает ускорение?

← →
Sha © (2010-09-17 09:59) [3]

Потому, что у тебя получается 2 независимых цепочки вычислений.
При развороте по 4 сумм все равно скорее всего 2х достаточно.
Это все для asm, для delphi может оказаться и не так.
Все зависит от того, как напишешь: если компилятор вздумает хранить
суммы не в регистрах, а на стеке, то можешь, наоборот, замедление получить.

← →
Zenith (2010-09-17 11:04) [4]

А что скажете по поводу этой библиотеки:

http://www.acedutils.narod.ru/

← →
Sha © (2010-09-17 11:23) [5]

>А что скажете по поводу этой библиотеки

Не смотрел, не знаю.

Сейчас проверил скорость суммирования.
На E6850 выгоды от развертывания и раздельного суммирования нет:
1375 ms против 1391 ms при погрешности 16 ms.
Так что наверно можно использовать что-нить вроде:

function GetSum1(pElem: pointer; Count: integer): integer;
begin;
Result:=0;
inc(integer(pElem),SizeOf(integer)*Count);
Count:=-Count;
while Count<0 do begin;
Result:=Result + pIntegerArray(pElem)[Count];
inc(Count);
end;
end;

← →
Sha © (2010-09-17 11:50) [6]

> Zenith (17.09.10 11:04) [4]

Сейчас бегло посмотрел то, что мне интересно, в этой библиотеке.
Понравилось.

Сортировка немного оптимизированная RTL, на ассемблере.
Но нет оптимизации выбором медианы трех и финальной сортировки вставками.
По идее, скоро на Королевстве статья должна быть, а пока можешь
под себя приспособить это http://guildalfa.ru/alsha/node/10

Поиск: FindFirstGE - есть, FindLastLE - нет.
Можешь взять здесь https://forums.embarcadero.com/thread.jspa?threadID=43335&tstart=0

← →
Sha © (2010-09-17 12:22) [7]

> Sha © (17.09.10 11:50) [6]

Аналог отсутствующей в AcedBinary.pas FindLastLe нашелся в AcedAlgorithm.pas.
Там же имеется IntroSort с вызовом сортировки вставками. Полезный юнит.
В целом от библиотеки очень приятное впечатление.

← →
Zenith (2010-09-17 13:03) [8]

> Sha © (17.09.10 11:50) [6]

Спасибо за статью!

← →
Pavia © (2010-09-17 15:02) [9]

> Sha © (17.09.10 11:23) [5]

Давно тестировал. У вас ошибка в расчетах чтение операция не параллельная.
Если взять массив байт то и складывать отдельно четные и нечетные то тормоза будут из за чтения. Что бы ускорение было надо читать в один регист самый большой. В зависимости от процессора 64бит в пентиуме, 128бит в core2due и 256бит на последних AMD

А не у кого нет класса для одномерного массива, а то SetLength тормозит из за того, что память очищает, а это не всегда нужно. Свой пока не написал.

← →
RWolf © (2010-09-17 15:55) [10]

толку от такой библиотеки… всё равно чтение из памяти на порядок медленнее суммирования.

← →
Sha © (2010-09-17 16:05) [11]

> Pavia © (17.09.10 15:02) [9]
> Давно тестировал. У вас ошибка в расчетах чтение операция не параллельная.

У меня не может быть ошибки )
Просто выигрыш в данном случае равен нулю, т.к. суммирование - быстрая операция.
Замени ее на СRC или векторное произведение и будет тебе выигрыш.

В общем случае параллелить надо то, что тормозит.
В данном случае это память и чисто паскальное решение не прокатит.

> а то SetLength тормозит из за того, что память очищает,

Не только из-за того.
Просто xрани количество занятых элементов и удлиняй, если не хватает.

← →
TUser © (2010-09-17 16:14) [12]

> 2. Сортировка - QuickSort.

В худшем случае квадратична )) Что есть лучшее для сортировки - зависит от конкретного случая, если действительно очень важна скорость.

← →
TUser © (2010-09-17 16:15) [13]

Скажем, еси большой массив, в свопе, то много раз обращаться к куче разных мест во всем массиве - это тормоза.

← →
Sha © (2010-09-17 16:22) [14]

> TUser © (17.09.10 16:14) [12]
> В худшем случае квадратична ))

Ты давно его видел, худший случай-то? Так что не надо болтать ерундой.

Это было актуально, когда худшим случаем был массив равных элементов.
Сейчас он другой немного, на практике не втречается.
Нужна голова, чтоб его сконструировать для атаки.

← →
Sha © (2010-09-17 16:29) [15]

> TUser © (17.09.10 16:15) [13]
> много раз обращаться к куче разных мест во всем массиве - это тормоза.

QuickSort - один из немногих алгоритмов, эффективно работающий с кеш-памятью.

← →
картман © (2010-09-17 17:52) [16]

ща памяти же много - почему никто не делает корневую сортировку?

← →
TUser © (2010-09-17 18:03) [17]

> Ты давно его видел, худший случай-то?

Совсем худший, не знаю, а вот ситуацию, когда QS не был оптимальным выбором видел. Да, конечно, чаще всего применяется либо это, либо пузырьковая сортировка, но это не значит же, что нет остального одного процента случаев. Я почему написал - автор просит очень очень быстро, а это автоматически означает, что надо не искать готовое универсальное решение, а разрабатывать конкретное под данную (неведомую нам) задачу.

> ща памяти же много

Много - это очень относительное понятие, мягко говоря. Тем паче, опять-таки, [16] с памятью работает по методу "а чего у нас там в байте номер random?"

← →
Sha © (2010-09-17 18:21) [18]

> картман © (17.09.10 17:52) [16]
> ща памяти же много - почему никто не делает корневую сортировку?

Не слышал, что за зверь?

> TUser © (17.09.10 18:03) [17]
> ситуацию, когда QS не был оптимальным выбором видел

QuickSort - сегодня наилучший общий алгоритм среди алгоритмов, основанных на сравнениях.
В конкретных случаях с малым диапазоном ключей лучше может оказаться RadixSort или подсчет,
в случае тяжелой функции сравнения и малой размерности - HeapSort,
но это скорее редкие исключения, о которых программист должен помнить.
Никто же не станет вызывать сортировку для пары чисел. Так и тут.

← →
Sha © (2010-09-17 18:36) [19]

Нашел. Корневая - еще одно название RadixSort, похоже.

← →
TUser © (2010-09-17 19:11) [20]

> Sha © (17.09.10 18:36) [19]
>
> Нашел. Корневая - еще одно название RadixSort, похоже.

Тоже искал ... вроде, это еще и то, что называется "цифровая" :)

главное, сложность О(N)

> Тоже искал ... вроде, это еще и то, что называется "цифровая"

А также "поразрядная".
Однажды с её помощью изрядно удивил преподавателя, когда оказалось, что мой алгоритм на больших массивах в полтора-два раза обгонял квиксорта.

> 0x00FF00 © (17.09.10 19:27) [22]
> мой алгоритм на больших массивах в полтора-два раза обгонял квиксорта.

Плохой QuickSort значит )

А если серьезно, то разных реализаций QuickSort до фига.
И различаться по скорости они могут в 1.5-2 раза.
Поэтому, например, некоторым реализациям DualPivotQuickSort
иногда удается обогнать некоторые реализации классической QuickSort.

> картман (17.09.2010 19:26:21) [21]

Самое быстрое пузырек, проверять на отсортированых данных, его никто не
обгонит.
Поэтому не оговаривая характер данных и не проверяя на заранее подобраных
наборах это неправилно.
Нужны минимум три набора для испытаний

1. с нормальным распределение
1. отсортированый в прямом порядке
1. отсортированый в обратном порядке

Это общее, из характера данных - для строк важен средний размер строки.
Некоторые алогритмы покажут противоположные результаты при длинных и
коротких строках. И так далее, нюансов много.

Зато пузырек лопнет на обратном порядке )

> Sha (17.09.2010 19:44:25) [25]

Вот поэтому и говорю, что испытания должны быть более полными с заранее
согласоваными наборами данных для проверки.

Всплывет - не всплывет.

взлетит )

> Anatoly Podgoretsky © (17.09.10 19:47) [26]

Кроме того, что ты назвал, в стандартный набор обычно включают повторяюшиеся данные, частично сортированные данные (сортированный и несортированный куски).

> Sha (17.09.2010 19:53:28) [28]

Ну у меня они шли под словом Другие и надо согласовывать набор исходныъ
данных, я думаю должно быть не менее 10 наборов.

Библиотека для быстрых операций с массивами Найти похожие ветки