Массивы.

← →
KIE © (2003-12-22 14:01) [0]

Кто знает как быстро сравнить два массива. Какие вообще есть быстрые методы оступа к массивам?

← →
Юрий Зотов © (2003-12-22 14:06) [1]

1. Например, CompareMem.
2. Адресация со смещением. IMHO, компилятор ее и использует.

← →
Digitman © (2003-12-22 14:09) [2]

var
Array1, Array2: String;
...
if Array1 = Array2 then ... else ...

чем не "быстрое сравнение массивов" ?

← →
Skier © (2003-12-22 14:10) [3]

>Digitman © (22.12.03 14:09) [2]
:))

← →
Digitman © (2003-12-22 14:13) [4]

> Skier

сейчас в меня помидоры полетят)

← →
REA © (2003-12-22 14:36) [5]

>Какие вообще есть быстрые методы оступа к массивам?

Есть относительно быстрый метод доступа по указателю без индексов. Можно хэши хранить и сравнивать сначала их.

← →
Anatoly Podgoretsky © (2003-12-22 14:42) [6]

Digitman © (22.12.03 14:13) [4]
Не за что, особенно учитывая вопрос.

← →
Ангел. © (2003-12-22 19:41) [7]

1. Есть понятие линейная сортировка.. линейный доступ - жрет кучу памяти но внекоторыХ! случаях можно использовать доступ к элементам прямой;) 2. Смотря что хранить - если возможно сделать табличную структуру массива.

Уточни вопрос...

← →
KIE © (2003-12-24 07:25) [8]

есть два массива A[x,y] и B[x1,y1]. "A" массив всегда больше "B". Хранятся в них единицы и ноли (Integer). Нам надо найти вхождение "B" массива в A. Причем делается так, берем B накладываем его на А, считаем, сколько точек несовпадает, вычисляем процент. Если процент несоответствия < 3 тогда считаем что B входит в A иначе .... делаем сдвиг B внутри A и проверяем дальше.

← →
OlDemon © (2003-12-24 08:20) [9]

2 KIE>
если массивы одинаковые то сравнивать можно методом DigitMen"a [2]. Но учитываю задачу, тебе это не подходит. Создай функцию которая выдает процент несоответсвия и в цикле отправляй туда координаты из массива А, по которым можно сформировать массив идентичный В.

← →
REA © (2003-12-24 09:58) [10]

Если перегнать массив в биты, то возможно некоторые операции удастся ускорить. Например логическое And даст совпадения по 8 точкам сразу.

← →
Sha © (2003-12-24 12:00) [11]

> KIE © (24.12.03 07:25) [8]
А что в массивах-то? Отпечатки пальцев, что ли?

← →
Digitman © (2003-12-24 12:18) [12]

> KIE © (24.12.03 07:25) [8]

ага... ну теперь понятно
и в чем у тебя сомнения ?

← →
Brahman © (2003-12-24 12:41) [13]

Алгоритмы быстрой свертки (основа БПФ и других теоретико-числовых преобразований).
По существу нужна двумерная корреляционная функция.

← →
KIE © (2003-12-24 16:41) [14]

Sha > ты почти прав!
Просто карта бывает большая, а искать надо быстро.

REA >> как с помощью AND можно проверить сразу 8 кординат?

← →
REA © (2003-12-24 17:06) [15]

Кто говорил про координаты?
Допустим в массиве A есть 00110101, а в массиве B 11110000.
Логическое And даст 00110000. Не знаю насколько это быстрее и насколько соответствует задаче, но как вариант может быть рассмотрено.

← →
Тимохов © (2003-12-24 17:10) [16]

Если все хранить в битах, то можно просто стравнивать побайтно командой "=".

← →
KIE © (2003-12-25 14:24) [17]

Тимохов >> я и сравниваю с помощью "=". Надо сказать долговато. На весь процесс сравнения у меня уходит около 3 секунд, а это достатоно много!

← →
Digitman © (2003-12-25 14:31) [18]

"быстрым сравнением массивов" в задаче и не пахнет

← →
Тимохов © (2003-12-25 14:32) [19]

1. Неясно, какого размера у тебя массивы.
У меня тоже была потребность делать что-то быстро.
Сравнивал CompareMem. Она вроде как на асме - поэтому не понял как она это делает. Возникло подозрение, что может она сравнивает побайтно, может лучше сравнивать сразу по двойным словам. Попробовал написал свою comparemem с сравнением по двойным словам - выигрыша не было.
2. Думаю, что врядли ты быстрее придумаешь алгоритм.
3. Думаю, что в каких-то случаях можно сравнивать crc32 двух больших структур. Но думаю, это сильно зависит от задачи.

← →
Тимохов © (2003-12-25 14:34) [20]

Кстати, никто не знает есть ли "аппаратное" сравнение двух областей памяти?

>>Тимохов >> я и сравниваю с помощью "=". Надо сказать долговато. На весь >>процесс сравнения у меня уходит около 3 секунд, а это достатоно много!

Самые быстрые операции - это логические используй операцию XOR если два числа равны = результат равен = 0, однозначно.
В CPU Pentium аппаратного сравнения памяти нет. Увы.

Большая карта, это черно-белое изображение, на котором что-то написано (напечатано), берем трафареты, т.е. малые массивы букв и цифр (43 штуки) и начинаем прогонять. Если совпадение есть то ... что то делаем, ели нет, то берем другой трафарет и поновой прокатываемся им по всей области "сканнируемого" изображения

Ну можно почитать в журнале "программист" об оптимизации доступа к памяти и использовании кэшей статьи Касперского. Весьма полезные рекомендации.
А дай ка код кстати - может что ускорим.

REA >> если я выложу исходники мне начальство башню повернёт на 360, оторвет и выбросит - коммерческая тайна. Ана словах, пробег я делаю старым классическим циклом for?а сравниваю через "="

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

← →
Algol (2003-12-26 18:15) [27]

> берем трафареты, т.е. малые массивы букв и цифр (43 штуки)
> и начинаем прогонять. Если совпадение есть то ...

Честно говоря сомневаюсь что простое сравнение в данном случае катит. Распознавание образов оч сложная задача, и уж простым сравнением с шаблоном точно не ограничивается ))

Нам то нужен всего небольшой кусок кода, чтобы мы всем скопом могли его оптимизировать.
Не даром на Руси говорят: одна голова хорошо, а две лучше! (хм три уже много.)

> Тимохов © (25.12.03 14:34) [20]

маш.инструкция rep[e/ne] cmps[b/w/d] и есть наилучший способ "аппаратного" сравнения

> KIE

> берем трафареты

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

Массивы. Найти похожие ветки