Гость
Войти | Профиль | Очистить
Целевая тема:
Создать новую тему:
Автор:
Действия ...
Форумы / Программирование [игнор отключен] [закрыт для гостей] / самый эффективный алгоритм поиска одинаковых элементов списка / 25 сообщений из 36, страница 1 из 2
  1  все
28.12.2007, 18:56
    #35040979
po4talyon
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
| Ответить | Цитировать | Написать  
28.12.2007, 19:05
    #35040989
Denis.
Denis.
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
самый эффективный алгоритм поиска одинаковых элементов списка
Может посмотреть в направлении квиксорта? Типа отсортировать, потом за один пробег посмотреть повторы... Это я так, не думая))) может и не прав)
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
28.12.2007, 19:18
    #35041006
mayton
mayton
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
самый эффективный алгоритм поиска одинаковых элементов списка
Или более общий случай - построение B+ индекса по списку.
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
28.12.2007, 19:21
    #35041010
po4talyon
po4talyon
Гость
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
самый эффективный алгоритм поиска одинаковых элементов списка
maytonИли более общий случай - построение B+ индекса по списку.

это как? Есть ссылка на этот алгоритм?
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
29.12.2007, 00:58
    #35041206
po4talyon
po4talyon
Гость
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
самый эффективный алгоритм поиска одинаковых элементов списка
есть еще предлолжения?
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
29.12.2007, 10:07
    #35041467
0xff
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
| Ответить | Цитировать | Написать  
29.12.2007, 11:54
    #35041697
ErV
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
| Ответить | Цитировать | Написать  
29.12.2007, 13:31
    #35042011
Frenzy
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
| Ответить | Цитировать | Написать  
Период между сообщениями больше года.
14.05.2012, 07:42
    #37792592
doubleich-11
doubleich-11
Гость
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
самый эффективный алгоритм поиска одинаковых элементов списка
Можете подсказать подобный поиск только на паскале?
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
14.05.2012, 15:10
    #37793343
Division X
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
| Ответить | Цитировать | Написать  
14.05.2012, 15:13
    #37793354
MasterZiv
MasterZiv
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
самый эффективный алгоритм поиска одинаковых элементов списка
po4talyon,

Надо бегать по спискам и добавлять в хэш-таблицу по критерию сравнения.
Это будет O(N1+N2) формально, фактически немного медленнее.
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
14.05.2012, 15:21
    #37793367
Division X
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
| Ответить | Цитировать | Написать  
14.05.2012, 15:25
    #37793379
Яростный Меч
Яростный Меч
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
самый эффективный алгоритм поиска одинаковых элементов списка
Division X,

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

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

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

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

В-первых, объем массива repeated в наихудшем случае (каждый элемент повторяется ровно два раза) получается ровно половина исходного, т.е. сложность уже падает вдвое. Во вторых, объекты реализованы как хэши. В-третьих, как потом обрабатывать результаты без портянок кода? ForEach и map для объекта не сделаешь, в отличие от массива.
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
14.05.2012, 15:48
    #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
| Ответить | Цитировать | Написать  
14.05.2012, 16:38
    #37793531
Division X
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
| Ответить | Цитировать | Написать  
16.05.2012, 23:04
    #37797920
Lepsik
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
| Ответить | Цитировать | Написать  
17.05.2012, 09:54
    #37798249
TVA_11
TVA_11
Гость
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
самый эффективный алгоритм поиска одинаковых элементов списка
Чтобы быстро найти все похожие элементы массива, надо его отсортировать.
После чего поиск будет очень быстрым.

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

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

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


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


П.С.
Ясно, что метод пузырька в одного огромной группе не эффективен.
Для определения размеров групп используются логарифмы.
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
17.05.2012, 11:35
    #37798477
k0rvin
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
| Ответить | Цитировать | Написать  
17.05.2012, 11:43
    #37798492
TVA_11
TVA_11
Гость
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
самый эффективный алгоритм поиска одинаковых элементов списка
k0rvin,

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

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

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

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

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

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

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

П.С.
Ясно, что метод пузырька в одного огромной группе не эффективен.
Для определения размеров групп используются логарифмы.Хоар, Шелл и прочие прошли мимо Вас?
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
  1  все
Форумы / Программирование [игнор отключен] [закрыт для гостей] / самый эффективный алгоритм поиска одинаковых элементов списка / 25 сообщений из 36, страница 1 из 2
Найденые пользователи ...
Разблокировать пользователей ...
Читали тему (0):
Читали форум (0):
Пользователи онлайн (0):
Польз. соглашение  
Полит. конфиден.  
созд. / загр.: 462ms
Закрыть
start [/forum/topic.php?fid=16&mobile=1&tid=1342260]:
 0ms
get settings:
 9ms
get forum list:
 15ms
check forum access:
 3ms
check topic access:
 3ms
track hit:
 158ms
get topic data:
 10ms
get forum data:
 2ms
get page messages:
 58ms
get tp. blocked users:
 1ms
others: 203ms
total:  462ms
x
x
Закрыть


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