Форум: "Основная";
Текущий архив: 2004.01.09;
Скачать: [xml.tar.bz2];

Вниз

Как можно БЫСТРО найти в массиве одинаковые числа ?   Найти похожие ветки 

← →
Кен   (2003-12-08 06:30) [0]

Медленно - это сравнивать всё со всем. Но если массив большой, то это долго. Компьютер как бы подвисает. Может есть какой алгоритм похитрее ?

---

← →
OlegGashev   (2003-12-08 06:37) [1]

Сортировка и сравнение рядом стоящих.

---

← →
OlegGashev   (2003-12-08 06:38) [2]

Сортировка и сравнение рядом стоящих.

---

← →
Кен   (2003-12-08 06:44) [3]

> OlegGashev © (08.12.03 06:37) [1]
> Сортировка и сравнение рядом стоящих.

Мне ненужна сортировка. Нужно чтобы элементы осталисть там, где стоят.

---

← →
OlegGashev   (2003-12-08 06:49) [4]

ок. создай массив с индексов элементов и переставляй во втором массиве.

---

← →
OlegGashev   (2003-12-08 06:49) [5]

ок. создай массив с индексов элементов и переставляй во втором массиве.

---

← →
Кен   (2003-12-08 06:51) [6]

> OlegGashev © (08.12.03 06:49) [4]
> ок. создай массив с индексов элементов и переставляй во
> втором массиве.

Это значит увеличить объём памяти вдвое.

---

← →
OlegGashev   (2003-12-08 06:51) [7]

Например, у тебя есть массив: 5 8 6 8
Берем массив индексов: 1 2 3 4

Делаем сортировку во втором, относительно первого массива.
Получим 1 3 2 4

2 и 4 совпадают. Это 8.

---

← →
OlegGashev   (2003-12-08 06:52) [8]

> Это значит увеличить объём памяти вдвое.

Достаточно грузить массив по частям.

---

← →
KSergey   (2003-12-08 08:37) [9]

> Кен © (08.12.03 06:51) [6]
> Это значит увеличить объём памяти вдвое.

Ну так уж наш мир создан: либо быстро, но много ресурсов, либо медленно, но мало ресурсов. ;)

---

← →
TUser   (2003-12-08 09:32) [10]

Если ты что-нибудь зшаешь о массиве, то может и быстрее получится. К примеру, если известно, что элементами массива могут быть только целые числа 1,2,...,n, то надо создать другой массив с соответствующим количеством элементов, и просмотреть исходный. Быстро и ресурсов мало, но только в таких частных случаях.

---

← →
Erik   (2003-12-08 13:56) [11]

1. А может нестоит от сортировки отказыватся?
2. Если у тебя элемент масива содержит запись, то можно применить такй вариант.
TPointElement = array of Pointer;

TMapSort = class
private
procedure Sort;
function GetValue(const Index: Pointer): Integer; virtual; abstract;
public
Map: TPointElement;
procedure Store; virtual; abstract;
end;

TXMLMapSort = class(TMapSort)
private
function GetValue(const Index: Pointer): Integer; override;
public
procedure Store(pArr: Pointer);
end;
В Sort ставим стандартный QuickSort
С оним изменением
while GetValue(Map[Lo]) < GetValue(Mid) do
Inc(Lo);
while GetValue(Map[Hi]) > GetValue(Mid) do
Далее думаю понятно.

---

← →
Кен   (2003-12-09 03:46) [12]

> Erik © (08.12.03 13:56) [11]


Я нашёл этот алгоритм QuickSort и мне он понравился : )
Просто никогда небыло необходимости что либо сортировать быстро.

С массивом некоторые проблемы. Он состоит из Integer. И дело в том, что он двухмерный. Состоит из большого количества строчек по 3 Integer в каждой. Я хотел находить в нём одинаковые строчки и заносить ссылки на их предыдущее вхождение в другой специаносозданный массив ссылок, а сами строчки обнулять. То есть если такая строка уже была найдена раньше, то на неё ставится ссылка, а сама строка обнуляется.

Например


№ массив массив ссылок
1 1 2 3 0
2 1 4 5 0
3 6 3 2 0
4 9 4 8 0
5 1 2 3 1 ( повторяет первый элемент массива )
6 6 3 2 3 ( повторяет третий элемент массива )
...
строки массива 5 и 6 позже обнуляются, а доступ к ним будет перенаправляться по ссылке.

Сижу думаю, как это реализовать через QuickSort . Что-то туго пока.

---

← →
Sam Stone   (2003-12-09 08:48) [13]

> Но если массив большой, то это долго. Компьютер как бы подвисает

вставь в цикл сортировки sleep(5)или Application.processmessages;

http://algolist.manual.ru/sort/index.php посмотри тут, может будет что полезное.

ЗЫ
А нельзя через маску узнать, есть ли одинаковые? Т.е. что-то типа myarray and <число>=<число>? Или это нереализуемо?

---

← →
Романов Р.В.   (2003-12-09 09:23) [14]

Это что то типа БД получается.
Составь отсортированный массив неповторяющихся элементов. И массив ссылок, т.е.
Исходный массив
№ массив
1 1 2 3
2 1 4 5
3 6 3 2
4 9 4 8
5 1 2 3
6 6 3 2

Сортированный массив
№ массив
1 1 2 3
2 1 4 5
3 6 3 2
4 9 4 8

Массив ссылок
№ массив
1 1
2 2
3 3
4 4
5 1
6 3

QuickSort можно прилепить для сортировки массива. Но думаю что для данного частного случая можно составить алгоритм и побыстрее.

---

← →
Кен   (2003-12-10 05:26) [15]

> Романов Р.В. © (09.12.03 09:23) [14]
> Это что то типа БД получается.
> Составь отсортированный массив неповторяющихся элементов.
>

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

Вот сам QuickSort : http://delphibase.endimus.com/?action=viewfunc&topic=mathsort&id=10088

---

← →
Романов Р.В.   (2003-12-10 08:55) [16]

> Тогда уж не отсортированный массив, а массив ссылок, на
> элементы массива в порядке возрастания

Зачем это???

---

← →
ALEIIIKA   (2003-12-10 10:08) [17]

1. Пример алгоритма быстрой сортировки есть в поставке Delphi:
...\Delphi6\Demos\Threads\
Еще бы посоветовал почитать книгу: "Алгоритмы: анализ и построение", там описано все или почти все.
2. А числа точно имеют тип Integer? Если тип Byte или Word, то можно в ассемблере из трех чисел сделать одно:
a := a + (a1 shl 8)+ (a2 shl 8)
Число получится трехбайтное, если используется тип Word то придется использовать регистры MMX, и уже потом сравнавать эти числа это будет намного быстрей.
3. Еще один способ вынести эту работу в отдельный поток (или несколдько потоков).

---

← →
Кен   (2003-12-13 07:40) [18]

> ALEIIIKA © (10.12.03 10:08) [17]
> 2. А числа точно имеют тип Integer?

Точно.

-------------

Вот программа которая получилась. В ней где то ошибка. Сортирует, но сортирует не правильно. Может кто найдёт ?

unit Unit1;

interface

uses
Windows, Messages, SysUtils, Variants, Classes, Graphics, Controls, Forms,
Dialogs, StdCtrls, ExtCtrls, ComCtrls, Placemnt;

type
TForm1 = class(TForm)
ListBox2: TListBox;
ListBox1: TListBox;
Button1: TButton;
procedure Button1Click(Sender: TObject);
private
{ Private declarations }
public
{ Public declarations }
end;

const
arrsize = 6;

var
Form1: TForm1;

Table : array[0..arrsize] of integer;
TInd : array[0..arrsize] of integer;

implementation

{$R *.dfm}

procedure TForm1.Button1Click(Sender: TObject);
var
i : Integer;

type
PIntArray = ^TIntArray;
TIntArray = array[0..0] of Integer;

procedure QuickSortM(IntArray, IndArr: PIntArray; Low, High: Integer);

procedure SwapInd(Index1, Index2: Integer);
var
N: Integer;
begin
N := IndArr[Index1];
IndArr[Index1] := IndArr[Index2];
IndArr[Index2] := N;
end;

var
Mid: Integer;
Item, Item0, i : Integer;
ScanUp, ScanDown: Integer;
begin
if High - Low <= 0 then exit;
if High - Low = 1 then begin
if IntArray[IndArr[High]] > IntArray[IndArr[Low]] then begin
SwapInd(Low, High);
end;
Exit;
end;
Mid := (High + Low) shr 1;
Item := IndArr[Mid];
Item0 := IntArray[IndArr[Mid]];
SwapInd (Mid, Low);
ScanUp := Low+1;
ScanDown := High;
repeat
while (ScanUp <= ScanDown) and (IntArray[IndArr[ScanUp]] >= Item0) do Inc(ScanUp);
while (IntArray[IndArr[ScanDown]] < Item0) do Dec(ScanDown);
if (ScanUp < ScanDown) then SwapInd(ScanUp, ScanDown);
until (ScanUp >= ScanDown);
IndArr[Low] := IndArr[ScanDown];
IndArr[ScanDown] := Item;
if (Low < ScanDown - 1) then QuickSortM(IntArray, IndArr, Low, ScanDown - 1);
if (ScanDown + 1 < High) then QuickSortM(IntArray, IndArr, ScanDown+1, High);
end;

begin
Randomize;

// Создаём массив случайных чисел.
for i := 0 to High(Table) do Table[i] := Random(9);
// Создаём массив индексов. Которые надо рассположить так, чтобы они указывали
// на числа от меньшего до большего.
for i := 0 to High(Table) do TInd[i] := i;

ListBox1.Items.Text := "TInd Table";
for i := 0 to High(Table) do ListBox1.Items.Add( IntToStr(TInd[i]) +" "
+IntToStr(Table[i]) );
Application.ProcessMessages;

QuickSortM(@Table, @TInd, 0, High(Table));

ListBox2.Items.Text := "TInd Table";
for i := 0 to High(Table) do ListBox2.Items.Add( IntToStr(TInd[i]) +" "
+IntToStr(Table[i]));
end;

end.

А вот форма :
object Form1: TForm1
Left = 260
Top = 113
Width = 496
Height = 357
Caption = "Form1"
Color = clBtnFace
Font.Charset = DEFAULT_CHARSET
Font.Color = clWindowText
Font.Height = -11
Font.Name = "MS Sans Serif"
Font.Style = []
OldCreateOrder = False
PixelsPerInch = 96
TextHeight = 13
object ListBox1: TListBox
Left = 0
Top = 0
Width = 160
Height = 324
Align = alLeft
ItemHeight = 13
TabOrder = 1
TabWidth = 10
end
object ListBox2: TListBox
Left = 160
Top = 0
Width = 153
Height = 324
Align = alLeft
ItemHeight = 13
TabOrder = 2
end
object Button1: TButton
Left = 336
Top = 32
Width = 75
Height = 25
Caption = "Button1"
TabOrder = 0
OnClick = Button1Click
end
end

---

← →
ALEIIIKA   (2003-12-15 10:58) [19]

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

unit Unit1;

interface

uses
Windows, Messages, SysUtils, Variants, Classes, Graphics, Controls, Forms,
Dialogs, StdCtrls;

type
TMas = record
i : Integer;
ind : Integer
end;
TForm1 = class(TForm)
ListBox1: TListBox;
ListBox2: TListBox;
Button1: TButton;
procedure Button1Click(Sender: TObject);
private
{ Private declarations }
public
{ Public declarations }
procedure Sort(var A: array of TMas);
procedure Sort1(var A: array of Integer);
end;

var
Form1: TForm1;
Table : array of TMas;
//????????????? ??????
Mas : array of Integer;

implementation

{$R *.dfm}

{ TQuickSort }
procedure TForm1.Sort(var A: array of TMas);

procedure QuickSort(var A: array of TMas; iLo, iHi: Integer);
var
Lo, Hi, Mid: Integer;
t : TMas;
begin
Lo := iLo;
Hi := iHi;
Mid := A[(Lo + Hi) div 2].i;
repeat
while A[Lo].i < Mid do Inc(Lo);
while A[Hi].i > Mid do Dec(Hi);
if Lo <= Hi then
begin
T := A[Lo];
A[Lo] := A[Hi];
A[Hi] := T;
Inc(Lo);
Dec(Hi);
end;
until Lo > Hi;
if Hi > iLo then QuickSort(A, iLo, Hi);
if Lo < iHi then QuickSort(A, Lo, iHi);
end;

begin
QuickSort(A, Low(A), High(A));
end;

procedure TForm1.Sort1(var A: array of Integer);

procedure QuickSort(var A: array of Integer; iLo, iHi: Integer);
var
Lo, Hi, Mid, T : Integer;
TT : TMas;
begin
Lo := iLo;
Hi := iHi;
Mid := A[(Lo + Hi) div 2];
repeat
while A[Lo] < Mid do Inc(Lo);
while A[Hi] > Mid do Dec(Hi);
if Lo <= Hi then
begin
T := A[Lo];
A[Lo] := A[Hi];
A[Hi] := T;
//
TT := Table[Lo];
Table[Lo] := Table[Hi];
Table[Hi] := TT;
//
Inc(Lo);
Dec(Hi);
end;
until Lo > Hi;
if Hi > iLo then QuickSort(A, iLo, Hi);
if Lo < iHi then QuickSort(A, Lo, iHi);
end;

begin
QuickSort(A, Low(A), High(A));
end;

procedure TForm1.Button1Click(Sender: TObject);
var
i : Integer;
T1 : TMas;
begin
Randomize;
SetLength(Table,6);
SetLength(Mas,6);
// ??????? ?????? ????????? ?????.
for i := 0 to High(Table) do
begin
Table[i].i := Random(9);
Table[i].ind := i;
end;
// ??????? ?????? ????????. ??????? ???? ???????????? ???, ????? ??? ?????????
// ?? ????? ?? ???????? ?? ????????.
for i := 0 to High(Mas) do Mas[i] := i;

ListBox1.Items.Text := "TInd Table";
for i := 0 to High(Table) do ListBox1.Items.Add(Format("%d %d",[Table[i].ind,Table[i].i]));

Sort(Table);

for i := Low(Table) to High(Table) do
Mas[i] := Table[i].ind;

for i := Low(Table) to High(Table) do
Table[i].ind := i;

Sort1(Mas);

ListBox2.Items.Text := "TInd Table";
for i := 0 to High(Table) do ListBox2.Items.Add(Format("%d %d",[Table[i].ind,Table[i].i]));

end;

end.


---

← →
Erik   (2003-12-15 11:25) [20]

А вобщето можно намного проще, берещ все числа заносиш в масив типа
MyRec = record;
Index: Integer;
Value: Integer;
end;
MySort = Array of MyRec;
Value значение твоего элемента, Index - индекс масива последовательно увеличиваеш при присвоениее элемента
Исходный массив
№ массив
1 1 2 3
2 1 4 5
3 6 3 2
4 9 4 8
5 1 2 3
6 6 3 2

Результирующий:
1 1
2 2
3 3
4 1
5 4
6 5
7 6
8 3
9 2
.....
Далее сортируеш по предложеному мной варианту (GetValue достает элемент из record). И проходиш циклом по отсортированому масиву сравнивая соседние числа.

---

← →
имя   (2003-12-15 14:32) [21]

Удалено модератором

---

← →
Кен   (2003-12-18 01:36) [22]

> ALEIIIKA © (15.12.03 10:58) [19]

Только хотел похвалить алгоритм, как нашёл в нём ошибку.
На форму кидается CheckBox, остальное также, только процедура Button1Click другая.

procedure TForm1.Button1Click(Sender: TObject);
const
len = 10000;
var
i : Integer;
T1 : TMas;
begin
ListBox2.Clear;
ListBox1.Clear;

Randomize;
SetLength(Table, len);
SetLength(Mas, len);

// Создаём массив случайных чисел.
// Заполняем массивы. Table[i].i - случайное число Table[i].ind - индекс.
for i := 0 to High(Table) do
begin
Table[i].i := Random(900);
Table[i].ind := i;
end;

for i := 0 to High(Mas) do Mas[i] := i;

//ListBox1.Items.Text := "TInd Table";
if High(Table) < 1000 then
for i := 0 to High(Table) do ListBox1.Items.Add(Format("6%d %d",[Table[i].ind,Table[i].i]))
else
for i := 0 to 10000 do ListBox1.Items.Add(Format("%6d %d",[Table[i].ind,Table[i].i]));

Sort(Table);

for i := Low(Table) to High(Table) do Mas[i] := Table[i].ind;
for i := Low(Table) to High(Table) do Table[i].ind := i;

Sort1(Mas);

//ListBox2.Items.Text := "TInd Table";
if High(Table) < 1000 then
for i := 0 to High(Table) do ListBox2.Items.Add(Format("%6d %d",[Table[i].ind,Table[i].i]))
else
for i := 0 to 10000 do ListBox2.Items.Add(Format("%6d %d",[Table[i].ind,Table[i].i]));

end;

procedure TForm1.CheckBox1Click(Sender: TObject);
begin
ListBox2.Sorted := CheckBox1.Checked;
end;

Кликаем на CheckBox и элементы сортируются. И тут становится видно, что вверху в нулевые элементы затесался какой то элемент 40014 . Но, похоже это ошибка данной реализации QuickSort. Чего то там не учтено.

---

← →
_drew_   (2003-12-18 03:29) [23]

Почитайте книжку дядюшки Вирта по структурам данных и алгоритмам.

---

← →
Space Rover   (2003-12-18 06:31) [24]

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

---

← →
ALEIIIKA   (2003-12-18 11:44) [25]

Да вообще-то все правильно за исключением одного
массив от 0 до 9999 а не от 0 до 10000, в нем всего 10000 элементов но последний нулевой это - 1, а 9999 это 10000-ый.

---

← →
ALEIIIKA   (2003-12-18 11:48) [26]

А алгоритм правильный. Хотя можно его еще доработать. Сортировать быстрой сортировкой пока массив не будет разбит на под массивы небольшой длины, а затем их сортировать другим алгоритмов (например выборкой), и время сбережешь, и уровень поднимешь.

---

← →
Holy   (2003-12-18 13:19) [27]

Вечный разговор... Если просто найти, т.е. сам факт...

var a: array [1..N] of integer;
kol_vo : array [min..max] of integer;

begin
for i:=1 to N do
begin
inc(kol_vo[a[i]]);
if kol_vo[a[i]])>1 then ShowMessage("Найдено - "+IntToStr(a[i]));
end
end;

N - кол-во элементов.
min..max - диапазон значений.

Конечно оптимальность спорна, но данный подход прост в реализации и не требует сортировки.

---

← →
Кен   (2003-12-19 01:52) [28]

> ALEIIIKA © (18.12.03 11:44) [25]
> Да вообще-то все правильно за исключением одного
> массив от 0 до 9999 а не от 0 до 10000, в нем всего 10000
> элементов

10000 элементов у меня и лобовым перебором за секунды пролетают. Речь то идёт именно о больших массивах.

-------------------

Эту тупую задачу я наконец-то доделал. Вот функция сортировки трёх массивов с помещением результата в индексный массив IndArr .
Три массива (Arr, Arr1, Arr2) исползуется вместо одного двухмерного только потому, что мне так удобнее. Можно считать их тремя колонками одного массива. В IndArr помещается сначала ссылка на максимульную строчку из этого двухмерного массива, потом на чуть меньше и так далее до минимума.

procedure QuickSortM3(Arr, Arr1, Arr2, IndArr: PIntArray; Low, High: Integer);

procedure SwapInd(Index1, Index2: Integer);
var
N: Integer;
begin
N := IndArr[Index1];
IndArr[Index1] := IndArr[Index2];
IndArr[Index2] := N;
end;

var
Mid: Integer;
Item, Item0, Item1, Item2, i : Integer;
ScanUp, ScanDown: Integer;
begin

if High - Low <= 0 then exit;
if High - Low = 1 then begin
if ( Arr[IndArr[High]] > Arr[IndArr[Low]] )
or ( (Arr[IndArr[High]] = Arr[IndArr[Low]]) and (Arr1[IndArr[High]] > Arr1[IndArr[Low]]) )
or ( (Arr[IndArr[High]] = Arr[IndArr[Low]]) and (Arr1[IndArr[High]] = Arr1[IndArr[Low]]) and (Arr2[IndArr[High]] > Arr2[IndArr[Low]]) )
then
begin
SwapInd(Low, High);
end;
Exit;
end;
Mid := (High + Low) shr 1;
Item := IndArr[Mid];
Item0 := Arr[IndArr[Mid]];
Item1 := Arr1[IndArr[Mid]];
Item2 := Arr2[IndArr[Mid]];
SwapInd (Mid, Low);
ScanUp := Low+1;
ScanDown := High;
repeat
while (ScanUp <= ScanDown) and ( (Arr[IndArr[ScanUp]] > Item0)
or ( (Arr[IndArr[ScanUp]] = Item0) and (Arr1[IndArr[ScanUp]] > Item1) )
or ( (Arr[IndArr[ScanUp]] = Item0) and (Arr1[IndArr[ScanUp]] = Item1) and (Arr2[IndArr[ScanUp]] >= Item2) )
) do Inc(ScanUp);
while ( (Arr[IndArr[ScanDown]] < Item0)
or ( (Arr[IndArr[ScanDown]] = Item0) and (Arr1[IndArr[ScanDown]] < Item1) )
or ( (Arr[IndArr[ScanDown]] = Item0) and (Arr1[IndArr[ScanDown]] = Item1) and (Arr2[IndArr[ScanDown]] < Item2) )
) do Dec(ScanDown);
if (ScanUp < ScanDown) then SwapInd(ScanUp, ScanDown);
until (ScanUp >= ScanDown);
IndArr[Low] := IndArr[ScanDown];
IndArr[ScanDown] := Item;
if (Low < ScanDown - 1) then QuickSortM3(Arr, Arr1, Arr2, IndArr, Low, ScanDown - 1);
if (ScanDown + 1 < High) then QuickSortM3(Arr, Arr1, Arr2, IndArr, ScanDown+1, High);
end;

Миллион у меня сортируется примерно за 10 секунд. Причём, что любопытно, если одинаковых чисел слишком много, то начинает тормозить.

const
arrsize = 1000000;

var
Table : array[0..arrsize] of integer;
Table1 : array[0..arrsize] of integer;
Table2 : array[0..arrsize] of integer;
TInd : array[0..arrsize] of integer;

...
Randomize;

LowPos := 4;
HighPos := High(Table)-1;
// Инициализация.
for i := LowPos to HighPos do begin
Table[i] := Random(200) +1;
Table1[i] := Random(200) +1;
Table2[i] := Random(200) +1;
TLink[i] := 0;
TInd[i] := i;
end;
// Вызов.
QuickSortM3(@Table, @Table1, @Table2, @TInd, LowPos, HighPos);

---

← →
ALEIIIKA   (2003-12-22 14:07) [29]

Да ты не понял, последний элемент не 10000, а 9999. Тогда все работает нормально.

---

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

Форум: "Основная";
Текущий архив: 2004.01.09;
Скачать: [xml.tar.bz2];

Наверх

Память: 0.54 MB
Время: 0.013 c