Текущий архив: 2005.11.20;
Скачать: CL | DM;

Вниз

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

← →
Arazel ©   (2005-11-01 17:56) [0]

Помогите сэтим разобратся...

У меня есть масив содержащий в себе уникальные значение!
И своевременно масив увиличивается или уменьшается...

теперь я хочу спросить как  получить прямой доступ
к определнному индексу масива если имея уникальное значение
которое содержится в масиве!

Сразу говорю:
- Объем масива неизвестен
- Где адрес(index) значение тоже неизвестно
- Масив может менять размер -/+
+ У нас есть значение которое хранится в масиве

Пока я пользуюсь методом перебора (For do)
но это слишком медленно для масива размером 10000 Int64
да ещё программа "гонит" при таком пойске...

Как можно моментально найти?

---

← →
Ораклиный глаз   (2005-11-01 18:41) [1]

Если массив несортирован, то забудь.

---

← →
programania ©   (2005-11-01 19:54) [2]

У меня 1000 000 int64  проверяет весь за 16 милиСек на C2800
если это не мгновенно то на asm можно
довести до 3-ех машинных команд на элемент

---

← →
Arazel ©   (2005-11-01 19:59) [3]

Ну  покажи как ты это  делаешь.

---

← →
programania ©   (2005-11-01 21:49) [4]

Когда выделил в отдельную процедуру стало еще быстрее
за 3.7 мСек так что getTickCount не поспевает
пришлось повторить 100 раз

{$R-,B-}
var
mt:array[1..1000000] of int64;
nz:int64;
tc,time:cardinal;

procedure TForm1.Button1Click(Sender: TObject);
var i,j:integer;
begin
for i:=1 to 1000000 do mt[i]:=random(1000000000);
ln:=mt[999990];
tc:=getTickCount;
nz:=0;
for j:=1 to 100 do
for i:=1 to 1000000 do if mt[i]=ln then begin
 nz:=i;
 break;
end;
time:=getTickCount-tc;
showMessage("Нашла "+intToStr(nz)+#13+intToStr(time)+" мсек");
end;


---

← →
PAVIA ©   (2005-11-01 23:54) [5]

Можно и моментально найти.
Только не много массив переделать.
Берем массив заданного размера. Пусть Max=10000. В качестве элемента массива делаем список.
type
PElement=^TElement;
TElement=record
  Next:PElement;
  id:int64;
  end;
var
a:array [0..Max-1]:PElement;
Пешим хэш-функцию. она должна равномерно распределять элементы в массиве. К примеру такую:

function Hesh(a:int64):integer;
var a,h,i:integer;
p:pchar;
begin
p:=@a;
h:=0;
for i:=0 to 7 do // проходим по всем байтам int64
h:=(h*314+byte(p[i])) mod Max;
end;
Для добавления( поиска) в массив делаем функцию которая будет заносить(забирать) значение в клетку(из клетки) с номером который мы получим от хеш.
a[Hesh(id)]
Функции напишишь сам.
Список нужен, чтобы обработать коллизии- столкновения в результате получения одинаковых Hesh.

---

Страницы: 1 вся ветка

Текущий архив: 2005.11.20;
Скачать: CL | DM;

Наверх

Память: 0.48 MB
Время: 0.044 c