| Форумы
ЧАТ |
Орешник |
|
| Форумы -» | Основная («Начинающим»)/ Базы / WinAPI / Компоненты / Сети / Media / Игры / Corba и COM / KOL / FreePascal / .Net / Прочее / RSDN.ORG |
|
| ||
|
|
Новости |
Поиск |
FAQ |
Статьи |
Книги |
Новости VCL
| | Форумы ЧАТ |
Орешник |
|
| |||
| |||
| |||
« предыдущая ветвь | форум | следующая ветвь »
Быстрые алгоритмы операций с массивами [D7]
cls © (2012-12-02 12:36:00)Товарищи, подскажите пожалуйста, есть ли быстрые алгоритмы для операций с массивами для сравнения элементов и дальнейших арифметических операций с ними (по условию). Все что я нашел, касается только разных сортировок. А, например, для преобразования элементов массива заданным образом остается только последовательный перебор всех элементов. При объеме в сотни элементов - это быстро, считанные секунды, а если сотня тысяч - уже долго (счет на минуты, иногда десятки минут). Есть ли способ ускорить такие операции, м.б. описано в какой-нибудь литературе?
cls (2012-12-02 15:06:00) [21]
> Юрий Зотов (02.12.12 14:21) [20]
>
>
> > cls (02.12.12 14:17) [19]
>
> Этот код выполняется практически мгновенно. Вы либо играете
> в партизанку на допросе, либо занимаетесь дешевым разводом.
>
Не было бы проблемы - не спрашивал бы.
cls (2012-12-02 14:49:00) [22]
> if ( Data[J].Z - MidArifm) < 0 then Data[J].NClass:= 0
> else Data[J].NClass:= 1;
Я так и делал - получил ошибку: Left side cannot be assigned to. Если брать временную переменную-рекорд (гонять туда-сюда), ошибки нет. В чем разница?
DVM (2012-12-02 14:25:00) [23]
> 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;
Юрий Зотов (2012-12-02 14:21:00) [24]
> cls (02.12.12 14:17) [19]
Этот код выполняется практически мгновенно. Вы либо играете в партизанку на допросе, либо занимаетесь дешевым разводом.
cls (2012-12-02 14:17:00) [25]Действительно, 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;
только это упрощенный вариант, но суть та же
DVM (2012-12-02 14:13:00) [26]
> RWolf (02.12.12 14:12) [17]
и даже его можно ускорить, но дело не в этом, автор утаивает детали
RWolf (2012-12-02 14:12:00) [27]
> [14]
на i5 этот код выполняется менее, чем за 1 мсек.
DVM (2012-12-02 14:08:00) [28]
> cls (02.12.12 14:05) [14]
бессмысленный код, он ничего не делает.
Юрий Зотов (2012-12-02 14:06:00) [29]
> 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;
Это выполняется мгновенно. Значит, Ваша реализация не нормальная. Показывайте код.
cls (2012-12-02 14:05:00) [30]
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;
DVM (2012-12-02 14:00:00) [31]
> cls
> Простой перебор элементов с операцией сравнения длится при
> объеме около 250000 элементов минут 10. Что может помочь?
>
напиши сюда алгоритм
RWolf (2012-12-02 13:49:00) [32]не могу представить сочетание железа, на котором такой перебор будет выполняться 10 минут. Даже БК-0010 справится быстрее; другое дело, что в ней просто нет памяти под массив из 250 тыс. элементов.
Этот массив подкачивается из базы данных на другом континенте, что ли?
brother (2012-12-02 13:45:00) [33]не путай алгоритм с его реализацией.
cls (2012-12-02 13:43:00) [34]
> Юрий Зотов
> в алгоритме их преобразования.
Например, приведенное выше преобразование: сравнить элементы массива А с заданной величиной и в массив В вывести результат (1 или 0). Простой перебор элементов с операцией сравнения длится при объеме около 250000 элементов минут 10. Что может помочь?
Авоськ (2012-12-02 13:29:00) [35]читай [5] несколько раз, авось, усвоится.
Юрий Зотов (2012-12-02 13:28:00) [36]
> cls (02.12.12 13:13) [6]
> есть литература, посвященная или касающаяся оптимальных алгоритмов
> обработки массивов?
1. Не массивов, а их элементов. Проблема в этом, как уже говорилось.
2. Как можно посоветовать литературу по оптимизации обработки чего-то, если неизвестно, что это за обработка?
DVM (2012-12-02 13:27:00) [37]
> cls (02.12.12 13:13) [6]
Дело тут не в массивах. Дело в алгоритмах. Литература то конечно есть, Кнут тот же например - там ты найдешь ответы на все вопросы. Но может конкретизировать вопрос, вот мол есть такой алгоритм, как его ускорить можно.
cls (2012-12-02 13:13:00) [38]
> но тут уж надо оптимизировать сами алгоритмы.
об этом и вопрос - есть литература, посвященная или касающаяся оптимальных алгоритмов обработки массивов?
Юрий Зотов (2012-12-02 13:13:00) [39]
> 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:11:00) [40]
> есть, конечно — GPU.
Каким образом? Если, например, нужно сравнить элементы с заданной величиной и результат внести в другой массив.
| |
Страницы: 