powered by simpleCommunicator - 2.0.61     © 2026 Programmizd 02
Целевая тема:
Создать новую тему:
Автор:
Закрыть
Цитировать
Форумы / Программирование [игнор отключен] [закрыт для гостей] / самый эффективный алгоритм поиска одинаковых элементов списка
36 сообщений из 36, показаны все 2 страниц
самый эффективный алгоритм поиска одинаковых элементов списка
    #35040979
po4talyon
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Гость
Всем привет.
Кто-нибудь знает самый эффективный алгоритм поиска одинаковых элементов списка ( массива) ?

То что есть пока, это вот:

Код: plaintext
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
     char[] List = { 'a', 'b', 'c', 'd','a','f','c' };
            string IterativeItems = "";
            int countOfIterations= 0 ;
            for (int i =  0 ; i < List.Length; ++i)
            {
                for (int j = i +  1 ; j < List.Length; ++j)
                {                    
                    if (List[i] == List[j])
                    {
                        IterativeItems += List[i];
                    }
                    ++countOfIterations;                    
                }
            }
            Console.WriteLine("IterativeItems=" + IterativeItems);
            Console.WriteLine("countOfIterations=" + countOfIterations.ToString());
            Console.Read();

Количество итераций для этого алгоритма (n^2 - n)/2
Есть предложения??:)
...
Рейтинг: 0 / 0
самый эффективный алгоритм поиска одинаковых элементов списка
    #35040989
Фотография Denis.
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Может посмотреть в направлении квиксорта? Типа отсортировать, потом за один пробег посмотреть повторы... Это я так, не думая))) может и не прав)
...
Рейтинг: 0 / 0
самый эффективный алгоритм поиска одинаковых элементов списка
    #35041006
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Или более общий случай - построение B+ индекса по списку.
...
Рейтинг: 0 / 0
самый эффективный алгоритм поиска одинаковых элементов списка
    #35041010
po4talyon
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Гость
maytonИли более общий случай - построение B+ индекса по списку.

это как? Есть ссылка на этот алгоритм?
...
Рейтинг: 0 / 0
самый эффективный алгоритм поиска одинаковых элементов списка
    #35041206
po4talyon
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Гость
есть еще предлолжения?
...
Рейтинг: 0 / 0
самый эффективный алгоритм поиска одинаковых элементов списка
    #35041467
0xff
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Ну, можно еще на хэшах сделать, примерно вот так:
Код: plaintext
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
use strict;
use warnings;

my @list = ('a', 'b', 'c', 'd','a','f','c');

my %hash = ();
my $iterative_times =  0 ;
foreach my $item(@list) {
  $iterative_times++ if defined $hash{$item};
  $hash{$item}="";
}

print $iterative_times;
...
Рейтинг: 0 / 0
самый эффективный алгоритм поиска одинаковых элементов списка
    #35041697
ErV
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
po4talyon wrote:

> есть еще предлолжения?
Если число возможных элементов ограничено (например, каждый элемент -
целое число до 32х бит (хотя лучше 16 , можно сделать битовое
множество. (правда, для 32хбитного числа на это уйдет ~512мб рам, но,
например, для char символов такой способ - самое оно.).

Т.е.
1) обнуляем битовое множество
2) создаем пустой список - результат
3) пробегаем исходный список, для каждого элемента, если соответствующий
бит не установлен, добавляем элемент в список-результат, устанавливаем
бит в единицу.
4) возвращаем список-результат.

количество операций равно количеству элементов, но на обнуление
множества при больших числах элементов уйдет порядочно времени. Т.е.
это неэффективно использовать для 3х..4х чисел int32, например.

Для других/емких типов данных просто нужно замену битовой карте, принцип
будет тот же.

Ну а если это не подходит, то останется только "сортировка, затем
перебор подряд".
--
We are all going to hell and I'm driving the bus
Posted via ActualForum NNTP Server 1.4
...
Рейтинг: 0 / 0
самый эффективный алгоритм поиска одинаковых элементов списка
    #35042011
Фотография Frenzy
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
вот примерно так можно сделать деревьями - можно добавить поле и считать в него сколько раз встретился тот или иной элемент.
сложность получится чтото вроде n*log2(n)/2 - от нее уже сложно уйти будет
суть в том чтобы избежать линейного поиска в твоем внутреннем цикле

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

на самом деле если это пишется на каком-нибудь интерпретируемом языке, то действительно быстрее будет посортировать кьюсортом который там скомпилирован

Код: plaintext
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
18.
19.
20.
21.
22.
23.
24.
25.
26.
27.
28.
29.
30.
31.
32.
33.
34.
35.
36.
37.
38.
39.
40.
41.
42.
43.
class BTreeNode {
    public int value;
    
    public BTreeNode leftNode  = null;
    public BTreeNode rightNode = null;
    
    public BTreeNode(int value) {
        this.value = value;
    }
    
    public int push(int value) {
        if (value < this.value)
            if (leftNode == null) {
                leftNode = new BTreeNode(value);
                return  0 ;
            }
            else return leftNode.push(value);
        
        if (value > this.value)
            if (rightNode == null) {
                rightNode = new BTreeNode(value);
                return  0 ;
            }
            else return rightNode.push(value);

        return  1 ;
    }
}

public class Main {

    public static void main(String[] args) {
        int numbers[] = { 1 , 6 , 4 , 3 , 8 , 6 , 7 , 5 , 3 , 4 , 2 , 5 , 1 , 0 , 7 , 8 , 5 , 9 , 7 , 8 , 3 };
        int totalIters =  0 ;
        
        BTreeNode root = new BTreeNode(numbers[ 0 ]);
        
        for(int i =  1 ; i < numbers.length; i++)
            totalIters += root.push(numbers[i]);
        
        System.out.println(totalIters);
    }

}

_______________________________________
2pro4U
...
Рейтинг: 0 / 0
Период между сообщениями больше года.
самый эффективный алгоритм поиска одинаковых элементов списка
    #37792592
doubleich-11
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Гость
Можете подсказать подобный поиск только на паскале?
...
Рейтинг: 0 / 0
самый эффективный алгоритм поиска одинаковых элементов списка
    #37793343
Division X
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Javascript (ECMAScript 5):
Код: javascript
1.
2.
3.
4.
5.
6.
7.
var list = [ 'a', 'b', 'c', 'd','a','f','c' ];
var repeated = [];
list.forEach(function(val,index,arr){
	if(arr.indexOf(val)!=arr.lastIndexOf(val) && repeated.indexOf(val)==-1)
		repeated.push(val)
	});
console.log(repeated);
...
Рейтинг: 0 / 0
самый эффективный алгоритм поиска одинаковых элементов списка
    #37793354
Фотография MasterZiv
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
po4talyon,

Надо бегать по спискам и добавлять в хэш-таблицу по критерию сравнения.
Это будет O(N1+N2) формально, фактически немного медленнее.
...
Рейтинг: 0 / 0
самый эффективный алгоритм поиска одинаковых элементов списка
    #37793367
Division X
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Хотя что-то хрень я написал. Можно даже так:
Код: javascript
1.
2.
3.
4.
5.
6.
7.
var list = [ 'a', 'b', 'c', 'd','a','f','c' ];
var repeated = [];
list.forEach(function(val,index,arr){
	if(index!=arr.lastIndexOf(val) && repeated.indexOf(val)==-1)
		repeated.push(val);
	});
console.log(repeated);
...
Рейтинг: 0 / 0
самый эффективный алгоритм поиска одинаковых элементов списка
    #37793379
Фотография Яростный Меч
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Division X,

для repeated правильнее использовать не массив, а объект.

-------------
а вообще, забавно. ТС задал вопрос 4 года назад, вопрос решили. doubleich-11 сейчас попросил то же, но на Паскале. Ну и последовали ответы, в духе форума
...
Рейтинг: 0 / 0
самый эффективный алгоритм поиска одинаковых элементов списка
    #37793382
Division X
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Яростный Мечдля repeated правильнее использовать не массив, а объект.

А эффективнее - массив.
...
Рейтинг: 0 / 0
самый эффективный алгоритм поиска одинаковых элементов списка
    #37793395
Фотография Яростный Меч
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Division XЯростный Мечдля repeated правильнее использовать не массив, а объект.

А эффективнее - массив.с массивом получаем О(N^2), а с объектом - О(N*lg(N)) (это если в движке объект реализован как дерево, если как хэштаблица, то другое, но явно меньше, чем поиск в массиве)
...
Рейтинг: 0 / 0
самый эффективный алгоритм поиска одинаковых элементов списка
    #37793408
Division X
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Яростный Меч,

В-первых, объем массива repeated в наихудшем случае (каждый элемент повторяется ровно два раза) получается ровно половина исходного, т.е. сложность уже падает вдвое. Во вторых, объекты реализованы как хэши. В-третьих, как потом обрабатывать результаты без портянок кода? ForEach и map для объекта не сделаешь, в отличие от массива.
...
Рейтинг: 0 / 0
самый эффективный алгоритм поиска одинаковых элементов списка
    #37793425
Фотография Яростный Меч
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Division X,

а, понял, repeated - это для результата.
всё равно я бы с доп. объектом сделал:
Код: javascript
1.
2.
3.
4.
5.
6.
7.
8.
9.
var list = [ 'a', 'b', 'c', 'd','a','f','c' ];
var repeated = [];
var map = {};
for(var i=0; i<list.length; ++i) {
	var co = map[list[i]]||0;
	map[list[i]] = co+1;
	if(co === 1) { repeated.push(list[i]); }
}
console.log(repeated);
...
Рейтинг: 0 / 0
самый эффективный алгоритм поиска одинаковых элементов списка
    #37793531
Division X
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Яростный Меч,

Хм. Тоже вариант:
Код: javascript
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
function getRepeats()
{
	var repeated = [];
	var items = {};
	list.forEach(function(val){
		if(items[val])
		{
			repeated.push(val);
			items[val]=0;
		}
		else items[val]=1;
		});
	return repeated;	
}
...
Рейтинг: 0 / 0
самый эффективный алгоритм поиска одинаковых элементов списка
    #37797920
Lepsik
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Код: plaintext
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
18.
19.
20.
void test16a()
{
    char listc[] = { 'a', 'b', 'c', 'd','a','f','c' };
    
    bool events[26] = {false};

    for( size_t i = 0; i < _countof(listc); i++ )
    {
        ptrdiff_t index = listc[i] - 'a';

        if( events[ index ] )
        {
            cout << listc[i] << " - ";
        }else
        {
            events[ index ] = true;
        }
    }

}
...
Рейтинг: 0 / 0
самый эффективный алгоритм поиска одинаковых элементов списка
    #37798249
TVA_11
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Гость
Чтобы быстро найти все похожие элементы массива, надо его отсортировать.
После чего поиск будет очень быстрым.

Если сотритровку учитывать, то нужен самый лучший алгоритм сортировки ).
...
Рейтинг: 0 / 0
самый эффективный алгоритм поиска одинаковых элементов списка
    #37798465
TVA_11
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Гость
Лучший алгоритм сортировки должен учитывать скорость обращения к элементу и количество элементов..
исходя из этого он

Разбивает все множество сортировки на N Групп
внутри которых идет сортировка методом пузырька.

Потом группы группируются в P больщих групп
внутри которых идет сортировка методом сортировки уже отсортированных групп


ну и так далее ).


П.С.
Ясно, что метод пузырька в одного огромной группе не эффективен.
Для определения размеров групп используются логарифмы.
...
Рейтинг: 0 / 0
самый эффективный алгоритм поиска одинаковых элементов списка
    #37798477
Фотография k0rvin
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
TVA_11Чтобы быстро найти все похожие элементы массива, надо его отсортировать.
После чего поиск будет очень быстрым.

Код: plaintext
1.
2.
3.
4.
5.
6.
7.
8.
9.
class Foo;

bool operator<(Foo &x, Foo &y) {
    return true;
}

bool operator>(Foo &x, Foo &y) {
    return true;
}


отсортируй пожалуйста массив объектов типа Foo.
...
Рейтинг: 0 / 0
самый эффективный алгоритм поиска одинаковых элементов списка
    #37798492
TVA_11
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Гость
k0rvin,

Самый простой метод сортировки по наименованию.

Строка(Foo &x) > Строка(Foo &Y)
...
Рейтинг: 0 / 0
самый эффективный алгоритм поиска одинаковых элементов списка
    #37798501
TVA_11
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Гость
k0rvin,

Если имеется ввиду, что

Возможно
Foo &x = Foo &y
Foo &x <> Foo &y

Невозможно
Foo &x > Foo &y
Foo &x < Foo &y
...
Рейтинг: 0 / 0
самый эффективный алгоритм поиска одинаковых элементов списка
    #37798557
Abstraction
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
TVA_11Лучший алгоритм сортировки должен учитывать скорость обращения к элементу и количество элементов..
исходя из этого он

Разбивает все множество сортировки на N Групп
внутри которых идет сортировка методом пузырька.

Потом группы группируются в P больщих групп
внутри которых идет сортировка методом сортировки уже отсортированных групп
ну и так далее ).

П.С.
Ясно, что метод пузырька в одного огромной группе не эффективен.
Для определения размеров групп используются логарифмы.Хоар, Шелл и прочие прошли мимо Вас?
...
Рейтинг: 0 / 0
самый эффективный алгоритм поиска одинаковых элементов списка
    #37798584
Фотография k0rvin
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
TVA_11Самый простой метод сортировки по наименованию.

Наименованию чего? Где ты в описании класса Foo видишь наименования?
...
Рейтинг: 0 / 0
самый эффективный алгоритм поиска одинаковых элементов списка
    #37798590
Фотография k0rvin
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
TVA_11имеется ввиду, что

Невозможно
Foo &x > Foo &y
Foo &x < Foo &y
Грубо говоря да. Только не "невозможно", а скорее неприменимо, бессмысленно.
...
Рейтинг: 0 / 0
самый эффективный алгоритм поиска одинаковых элементов списка
    #37798678
TVA_11
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Гость
k0rvin,

Если можно сравнить, тогда сортируй и будешь очень быстро искать одинаковые.
Главное, чтобы была возможность сравнить.
...
Рейтинг: 0 / 0
самый эффективный алгоритм поиска одинаковых элементов списка
    #37798691
TVA_11
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Гость
AbstractionTVA_11Лучший алгоритм сортировки должен учитывать скорость обращения к элементу и количество элементов..
исходя из этого он

Разбивает все множество сортировки на N Групп
внутри которых идет сортировка методом пузырька.

Потом группы группируются в P больщих групп
внутри которых идет сортировка методом сортировки уже отсортированных групп
ну и так далее ).

П.С.
Ясно, что метод пузырька в одного огромной группе не эффективен.
Для определения размеров групп используются логарифмы.Хоар, Шелл и прочие прошли мимо Вас?

Это все частные случаи.
При Числе элементов стремящемся к большим числам, все равно приходится разбивать на группы.
...
Рейтинг: 0 / 0
самый эффективный алгоритм поиска одинаковых элементов списка
    #37798729
Abstraction
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
TVA_11Abstractionпропущено...
Хоар, Шелл и прочие прошли мимо Вас?

Это все частные случаи.
При Числе элементов стремящемся к большим числам, все равно приходится разбивать на группы.Но не пузырьком же сортировать в больших группах, в самом-то деле? А так да, если массив настолько здоровый, что не лезет в память целиком, в ход идут немного другие алгоритмы. Но там для "определения размеров групп" опираются не на логарифмы, а на то, сколько в память влезает.
...
Рейтинг: 0 / 0
самый эффективный алгоритм поиска одинаковых элементов списка
    #37798844
TVA_11
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Гость
Abstraction,

Метод является существенно улучшенным вариантом алгоритма сортировки с помощью прямого обмена (его варианты известны как


«Пузырьковая сортировка», известного, в том числе, своей низкой эффективностью.


Принципиальное отличие состоит в том, что после каждого прохода элементы делятся на две независимые группы. Любопытный факт: улучшение самого неэффективного прямого метода сортировки дало в результате эффективный улучшенный метод.
...
Рейтинг: 0 / 0
самый эффективный алгоритм поиска одинаковых элементов списка
    #37798957
TVA_11
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Гость
Abstraction,

Ты не обижайся пожалуйста, я мало знаю и много шучу ),
...
Рейтинг: 0 / 0
самый эффективный алгоритм поиска одинаковых элементов списка
    #37799045
Фотография k0rvin
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
TVA_11Если можно сравнить, тогда сортируй и будешь очень быстро искать одинаковые.
Главное, чтобы была возможность сравнить.

Нет, спасибо, я воспользуюсь хешем и найду повторяющиеся тоже достаточно быстро.
...
Рейтинг: 0 / 0
самый эффективный алгоритм поиска одинаковых элементов списка
    #37799169
TVA_11
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Гость
k0rvinTVA_11Если можно сравнить, тогда сортируй и будешь очень быстро искать одинаковые.
Главное, чтобы была возможность сравнить.

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


Достаточно быстро - это одно.
А вот если не будет устраивать.., то

всегда есть возможность отсортировать и

в один проход найти все одинаковые элементы. Что мешает то!?
...
Рейтинг: 0 / 0
самый эффективный алгоритм поиска одинаковых элементов списка
    #37799191
Фотография k0rvin
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
TVA_11Достаточно быстро - это одно.
А вот если не будет устраивать.., то

всегда есть возможность отсортировать и

в один проход найти все одинаковые элементы. Что мешает то!?

хеш -- это и есть найти все повторяющиеся в один проход, а у тебя еще сортировка.
...
Рейтинг: 0 / 0
самый эффективный алгоритм поиска одинаковых элементов списка
    #37800048
Aleksandr Sharahov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
TVA_11улучшение самого неэффективного прямого метода сортировки дало в результате эффективный улучшенный метод.

улучшение автомобиля привело к созданию самолета
...
Рейтинг: 0 / 0
36 сообщений из 36, показаны все 2 страниц
Форумы / Программирование [игнор отключен] [закрыт для гостей] / самый эффективный алгоритм поиска одинаковых элементов списка
Найденые пользователи ...
Разблокировать пользователей ...
Читали форум (0):
Пользователи онлайн (0):
x
x
Закрыть


Просмотр
0 / 0
Close
Debug Console [Select Text]