Быстрые алгоритмы операций с массивами

← →
cls (2012-12-02 12:36) [0]

Товарищи, подскажите пожалуйста, есть ли быстрые алгоритмы для операций с массивами для сравнения элементов и дальнейших арифметических операций с ними (по условию). Все что я нашел, касается только разных сортировок. А, например, для преобразования элементов массива заданным образом остается только последовательный перебор всех элементов. При объеме в сотни элементов - это быстро, считанные секунды, а если сотня тысяч - уже долго (счет на минуты, иногда десятки минут). Есть ли способ ускорить такие операции, м.б. описано в какой-нибудь литературе?

← →
Авоськ (2012-12-02 12:57) [1]

> только последовательный перебор всех элементов

можно через один. авось, не заметят.

← →
RWolf (2012-12-02 13:01) [2]

есть, конечно — GPU.

← →
DVM (2012-12-02 13:09) [3]

> При объеме в сотни элементов - это быстро, считанные секунды,
> а если сотня тысяч - уже долго (счет на минуты, иногда
> десятки минут).

Сотня тысяч - это смехотворное количество без всяких GPU. Картинка FullHD - это 2 000 0000 элементов, и она тем не менее выводится на экран много раз в секунду и даже без GPU. Конечно все зависит от того, что за преобразования надо выполнять, но тут уж надо оптимизировать сами алгоритмы. GPU - это уже крайний случай, когда остальные возможности по оптимизации исчерпаны. GPU то он конечно быстро обрабатывает данныые, если суметь распараллелить задачу, это во первых надо суметь, а во-вторых, GPU тоже данные надо передать, а это время.

← →
cls (2012-12-02 13:11) [4]

> есть, конечно — GPU.

Каким образом? Если, например, нужно сравнить элементы с заданной величиной и результат внести в другой массив.

← →
Юрий Зотов (2012-12-02 13:13) [5]

> cls (02.12.12 12:36)
> для преобразования элементов массива заданным образом остается
> только последовательный перебор всех элементов. При объеме в сотни
> элементов - это быстро, считанные секунды, а если сотня тысяч - уже
> долго (счет на минуты, иногда десятки минут). Есть ли способ ускорить
> такие операции

Сам по себе, проход в цикле по сотне тысяч элементам массива не занимает много времени. И вот доказательство (миллион элементов):
type // TElementType = string; // 45..65 ms TElementType = integer; // 0..15 ms var A: array[1..1000000] of TElementType; N: TElementType; procedure TForm1.FormDblClick(Sender: TObject); var i: integer; T: cardinal; begin T := GetTickCount; for i := Low(A) to High(A) do N := A[i]; Caption := IntToStr(GetTickCount - T); end;
Проход по миллиону элементов типа Integer (а это один из самых быстрых типов, если вообще не самый быстрый) длится от 0 до 15 ms.

Проход миллиону элементов типа String (а это один из самых медленных типов, если вообще не самый медленный) длится от 45 до 65 ms.

Для других типов элементов время прохода должно быть примерно между этими граничными оценками.

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

Это все, что можно подсказать, не зная самого алгоритма.

← →
cls (2012-12-02 13:13) [6]

> но тут уж надо оптимизировать сами алгоритмы.

об этом и вопрос - есть литература, посвященная или касающаяся оптимальных алгоритмов обработки массивов?

← →
DVM (2012-12-02 13:27) [7]

> cls (02.12.12 13:13) [6]

Дело тут не в массивах. Дело в алгоритмах. Литература то конечно есть, Кнут тот же например - там ты найдешь ответы на все вопросы. Но может конкретизировать вопрос, вот мол есть такой алгоритм, как его ускорить можно.

← →
Юрий Зотов (2012-12-02 13:28) [8]

> cls (02.12.12 13:13) [6]
> есть литература, посвященная или касающаяся оптимальных алгоритмов
> обработки массивов?

1. Не массивов, а их элементов. Проблема в этом, как уже говорилось.

2. Как можно посоветовать литературу по оптимизации обработки чего-то, если неизвестно, что это за обработка?

← →
Авоськ (2012-12-02 13:29) [9]

читай [5] несколько раз, авось, усвоится.

← →
cls (2012-12-02 13:43) [10]

> Юрий Зотов

> в алгоритме их преобразования.

Например, приведенное выше преобразование: сравнить элементы массива А с заданной величиной и в массив В вывести результат (1 или 0). Простой перебор элементов с операцией сравнения длится при объеме около 250000 элементов минут 10. Что может помочь?

← →
brother (2012-12-02 13:45) [11]

не путай алгоритм с его реализацией.

← →
RWolf (2012-12-02 13:49) [12]

не могу представить сочетание железа, на котором такой перебор будет выполняться 10 минут. Даже БК-0010 справится быстрее; другое дело, что в ней просто нет памяти под массив из 250 тыс. элементов.
Этот массив подкачивается из базы данных на другом континенте, что ли?

← →
DVM (2012-12-02 14:00) [13]

> cls

> Простой перебор элементов с операцией сравнения длится при
> объеме около 250000 элементов минут 10. Что может помочь?
>

напиши сюда алгоритм

← →
cls (2012-12-02 14:05) [14]

Type TPointRecord X, Y, Z: single; NClass: integer; end; var Data: array of TPointRecord; P: TPointRecord; ..... for J:= 0 to Length(Data)-1 do //по всему массиву begin P:= Data[J]; //MidArifm уже посчитано if (P.Z - MidArifm) < 0 then P.NClass:= 0 else P.NClass:= 1; end;

← →
Юрий Зотов (2012-12-02 14:06) [15]

> cls (02.12.12 13:43) [10]
> сравнить элементы массива А с заданной величиной и в массив В вывести
> результат (1 или 0). Простой перебор элементов с операцией сравнения
> длится при объеме около 250000 элементов минут 10.

При нормальной реализации такого не должно быть.
type TElementType = cardinal; const MinIndex = 1; MaxIndex = 250000; ValueToCompare = High(TElementType) div 2; var A: array[MinIndex..MaxIndex] of TElementType; B: array[MinIndex..MaxIndex] of byte; procedure TForm1.FormDblClick(Sender: TObject); var i: integer; T: cardinal; begin T := GetTickCount; for i := Low(A) to High(A) do if A[i] > ValueToCompare then B[i] := 1 else B[i] := 0; Caption := IntToStr(GetTickCount - T); end;
Это выполняется мгновенно. Значит, Ваша реализация не нормальная. Показывайте код.

← →
DVM (2012-12-02 14:08) [16]

> cls (02.12.12 14:05) [14]

бессмысленный код, он ничего не делает.

← →
RWolf (2012-12-02 14:12) [17]

> [14]

на i5 этот код выполняется менее, чем за 1 мсек.

← →
DVM (2012-12-02 14:13) [18]

> RWolf (02.12.12 14:12) [17]

и даже его можно ускорить, но дело не в этом, автор утаивает детали

← →
cls (2012-12-02 14:17) [19]

Действительно, 1 оператор выпал
Type TPointRecord X, Y, Z: single; NClass: integer; end; var Data: array of TPointRecord; P: TPointRecord; ..... for J:= 0 to Length(Data)-1 do //по всему массиву begin P:= Data[J]; //MidArifm уже посчитано if (P.Z - MidArifm) < 0 then P.NClass:= 0 else P.NClass:= 1; Data[J]:= P; end;
только это упрощенный вариант, но суть та же

← →
Юрий Зотов (2012-12-02 14:21) [20]

> cls (02.12.12 14:17) [19]

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

← →
DVM (2012-12-02 14:25) [21]

> cls (02.12.12 14:17) [19]

этот код тоже будет выполняться считанные миллисекунды.

Но что могу сказать. Зачем туда - сюда гонять содержимое каждого элемента?

P:= Data[J]; if (P.Z - MidArifm) < 0 then P.NClass:= 0 else P.NClass:= 1; Data[J]:= P;

Заменить на

if ( Data[J].Z - MidArifm) < 0 then Data[J].NClass:= 0 else Data[J].NClass:= 1;

А еще лучше так:

Type
PPointRecord = ^TPointRecord;

var P: PPointRecord; P := @Data[J]; if ( P^.Z - MidArifm) < 0 then P^.NClass:= 0 else P^.NClass:= 1;

← →
cls (2012-12-02 14:49) [22]

> if ( Data[J].Z - MidArifm) < 0 then Data[J].NClass:= 0
> else Data[J].NClass:= 1;

Я так и делал - получил ошибку: Left side cannot be assigned to. Если брать временную переменную-рекорд (гонять туда-сюда), ошибки нет. В чем разница?

← →
cls (2012-12-02 15:06) [23]

> Юрий Зотов (02.12.12 14:21) [20]
>
>
> > cls (02.12.12 14:17) [19]
>
> Этот код выполняется практически мгновенно. Вы либо играете
> в партизанку на допросе, либо занимаетесь дешевым разводом.
>

Не было бы проблемы - не спрашивал бы.

← →
DVM (2012-12-02 15:08) [24]

> cls (02.12.12 14:49) [22]

> В чем разница?

В том что ты чего то скрываешь. Создай пустой проект, скопируй минимально необходимый проблемный код, убедись в наличии проблемы и ЛИШЬ ПОТОМ задавай вопрос и приводи код.

← →
Юрий Зотов (2012-12-02 15:25) [25]

> cls (02.12.12 15:06) [23]
> Не было бы проблемы - не спрашивал бы.

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

Значит, Вы показываете не тот код. Возникает вопрос - почему?

Одно из двух - либо не читаете того, что Вам пишут, либо нарочно.

← →
Styx (2012-12-02 15:38) [26]

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

← →
cls (2012-12-02 16:41) [27]

> Styx

В записи ровно столько, сколько написано

> Юрий Зотов

Я читаю все, что пишут все участники дискуссии, даже плоские шуточки, и ничего не скрываю. Весь код приводить нереально, поэтому я и привожу его в сокращенном виде. Вам поможет, если я приведу описание класса полностью:

//-------------------- Запись для одной точки ---------------------------------- TPointRecord = record X: double; // координаты X Y: double; // Y Z: single; // параметр NClass: integer;// номер класса после классификации end; //-------------------- TDataClass ---------------------------------------------- TGridSize = record //размер грида nX: integer; // кол-во профилей (столбцов матрицы) nY: integer; // кол-во пикетов (строк матрицы) end; TValueRecord = record //пара значений "минимум-максимум" LoVal: double; //минимум HiVal: double; //максимум end; TDataClass = class private FName: string; FChecked: boolean; FGridSize: TGridSize; FXSize: TValueRecord; FYSize: TValueRecord; FZSize: TValueRecord; FRotation: double; FBlank: double; FData: array of TPointRecord; FFileName: TFileName; protected procedure PutItem(AIndex: integer; AValue: TPointRecord); function GetItem(AIndex: integer): TPointRecord; procedure SetName(AName: string); procedure SetState(AState: boolean); procedure SetGridSize(AGridSize: TGridSize); procedure SetXSize(AValueRecord: TValueRecord); procedure SetYSize(AValueRecord: TValueRecord); procedure SetZSize(AValueRecord: TValueRecord); function GetStepX: double; function GetStepY: double; procedure SetRotation(ARotation: double); procedure SetBlank(ABlank: double); function GetItemCount: integer; function GetNumberNoEmpty: integer; function CalcMidArifm: extended; function CalcDispersy: extended; function CalcStDeviation: extended; procedure SetFileName(AFileName: TFileName); function CalcIntStergess: double; function CalcIntSqrtRootN: double; public //SignClass: array of String; constructor Create(ASize: integer); procedure ReadGrid(AFileName: TFileName); procedure WriteGrid(AFileName: TFileNAme; AOption: TOption); function CalcHistogram(AInterval: TInterval): THistogramArray; function ShowInfo: TStrings; property Name: string read FName write SetName; property Checked: boolean read FChecked write SetState; property GridSize: TGridSize read FGridSize write SetGridSize; property XSize: TValueRecord read FXSize write SetXSize; property YSize: TValueRecord read FYSize write SetYSize; property ZSize: TValueRecord read FZSize write SetZSize; property StepX: double read GetStepX; property StepY: double read GetStepY; property Rotation: double read FRotation write SetRotation; property Blank: double read FBlank write SetBlank; property Data[IndexOf: integer]:TPointRecord read GetItem write PutItem; property Count: integer read GetItemCount; property MidArifm: extended read CalcMidArifm; property Dispersy: extended read CalcDispersy; property StDeviation: extended read CalcStDeviation; property FileName: TFileName read FFileName write SetFileName; property IntStergess: double read CalcIntStergess; property IntSqrtRootN: double read CalcIntSqrtRootN; end;
и далее, со всеми методами, и прочая, и прочая...
Я лишь выделил проблему

← →
icWasya (2012-12-02 16:57) [28]

Фишка наверное в этом
property Data[IndexOf: integer]:TPointRecord read GetItem write PutItem;
а это не массив, а индексированное свойство.

← →
Anatoly Podgoretsky (2012-12-02 16:59) [29]

Автор боится за код, украдут и выдадут за свой.
Но кому он нужен такой медленный.

← →
Авоськ (2012-12-02 17:01) [30]

> Anatoly Podgoretsky (02.12.12 16:59) [29]

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

> cls (02.12.12 16:41) [27]

Если Вы читаете все, то должны были прочитать и [24]. И понять, что нужен не весь, а только минимальный проблемный код. И как его получить, там тоже написано.

Вы же вместо него приводите объявление класса и НИ ОДНОЙ строчки исполнимого кода. А тот исполнимый код, что Вы уже показывали, никаких проблем со скоростью не имеет. В результате нужной информации снова нет и снова ничего сказать нельзя.

Сделайте уже, наконец, то, что нужно было сделать сразу - покажите тот кусок РЕАЛЬНОГО кода, который ДЕЙСТВИТЕЛЬНО вызывает проблему. И РЕАЛЬНЫЕ объявления ВСЕХ переменных которые в этом куске участвуют.

← →
cls (2012-12-02 18:05) [32]

Мой код никому, кроме меня, не нужен, со всеми недостатками. Так что извините за беспокойство.

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

← →
Styx (2012-12-02 18:45) [34]

> RWolf © (02.12.12 18:23) [33]
> ну почему, я бы, например, с удовольствием посмотрел, как
> удалось тривиальный код ненамеренно замедлить

Дык вроде разобрались:

> icWasya (02.12.12 16:57) [28]
> Фишка наверное в этом
> property Data[IndexOf: integer]:TPointRecord read GetItem
> write PutItem;
> а это не массив, а индексированное свойство.

> Styx (02.12.12 18:45) [34]

> Дык вроде разобрались:
>

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

> [34]

ну хорошо, 200 мсек на i3, до 10 минут всё равно ой как далеко.

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

← →
Styx (2012-12-02 20:02) [38]

> конечно надо бы видеть, что происходит внутри у них

Коли код "снаружи" такой, как привёл ТС - значит, искать тормоза остаётся только как раз там...

← →
Palladin (2012-12-02 23:11) [39]

Вопрошатель решает конкретную задачу, что бы получить за нее конкретные деньги, а вы до сих пор не помогли ему их получить. Задаете глупые вопросы и рассказываете про сферические циклы в вакууме. А еще мастера.

← →
Slym (2012-12-03 08:38) [40]

в итоге все упрется в
SetLength(Data,Length(Data)+1); Data[Length(Data)-1]:=P;
:)

← →
Авоськ (2012-12-03 18:25) [41]

> Palladin (02.12.12 23:11) [39]
>
> А еще мастера.

Разве ты не слышал байку про то, как жена одного физика попросила этого самого физика ветку у дерева в саду спилить, мешавшую ей?

← →
Sapersky (2012-12-03 20:32) [42]

Мой телепатор говорит - там вывод для отладки в визуальный компонент, что-то вроде Memo1.Lines.Add...

← →
Очень Злой (2012-12-03 22:16) [43]

> Товарищи, подскажите пожалуйста, есть ли быстрые алгоритмы
> для операций с массивами для сравнения элементов и дальнейших
> арифметических операций с ними (по условию). Все что я нашел,
> касается только разных сортировок. А, например, для преобразования
> элементов массива заданным образом остается только последовательный
> перебор всех элементов.

ИМХО "быстрые" алгоритмы существуют для тех операций, где используется много проходов по масиву, и которые и существуют для того, чтобы уменьшить кол-во обращений к каждому из элементов массива, а если Вы собираетесь произвести какие-то операции над содержимым ячеек, где каждая ячейка используется 1 раз (для извлечения ее значения и возможно последующей записи нового значения), то таких каких-либы "быстрых" алгоритмов для этого по определению не может существовать.

Изредка такие операции можно немного ускорить, но это уже с помощью реализации. например если array of byte нужно проксорить с одним и тем же числом, то возможно быстрее будет брать из массива значения не побайтно, а например сразу по 4 байта в integer.

Хотя не зная реальной задачи - навряд-ли можно что-то сказать по сабжевому поводу...

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