Войти
ПрограммированиеФорумОбщее

Как быстро искать минимальный элемент в массиве с 400 000 числами???

Страницы: 1 2 3 Следующая »
#0
0:37, 25 авг. 2009

Привет всем!
Алгоритм следующий:
1) извлечь(удалить) из множества ключей минимальный
2) изменить значение одного ключа из множества
3) если в множестве более 4 ключей перейти к 1 пункту

Количество эл. в множестве 400 000. Какую необходимо использовать структуру данных чтобы реализовать данный алгоритм максимально быстро??


#1
0:39, 25 авг. 2009

можно хранить их в хипе. первая операция выполняется за O(1), вторая и третья - за O(log(n))

#2
1:40, 25 авг. 2009

непонятно что такое пункт 3, обясни подробней, а то у тебя 400к то у тебя не больше 4 :)

а так std::map тебе в руки )

1)

std::map<int,int> m;
m.erase( m.begin() );

2)

m[key] = new_value;

#3
6:21, 25 авг. 2009

Ну ты мог бы использовать кч-дерево... биты управляли бы какую ветку выбрать.
Тогда у тебя итераций больше чем разрядность чисел не было бы. Хотя с коллизиями я не знаю как быть. Хотя можно было бы сделать массив или каунтер на кол-во таких элементов. Как тебе идея?

Эээ... так вроде там и есть кч-дерево? в мапе стловском...

#4
7:07, 25 авг. 2009

Можно ускорить операцию в 100 000 раз.  Выбрать 4 максимальных по значению элемента. Остальное удалить.

#5
10:50, 25 авг. 2009

Я пишу на делфи.....
первый пункт - удалили минимальный элемент....это значит стало 399 999 элементов, потом дошли до 3 п.  399 999 > 4, вернулись на 1, удалили еще один элемент....стало 399 999

#6
10:51, 25 авг. 2009

наскоко я понимаю множество имеет 256 елементов, как вы туда 400 000 закуячити? или я чего то не понимаю :)

#7
10:58, 25 авг. 2009

нельзя все понимать буквально))....под множеством я массив имел ввиду...

#8
11:17, 25 авг. 2009

Megabyte-Ceercop

уточни пожалуйста....

Вот как я понял твои слова.....
выбираю 4 наименьших эл из 400 000, беру минимальный....удаляю его...изменяю значения одного из 400 000, как мне теперь найти тот который я должен добавить к тем 4 чтобы их стало снова 4(я же один удалил - стало 3)...за какое время я это по твоему смогу сделать??

#9
11:39, 25 авг. 2009

Если массив должен оставаться массивом, то для ускорения поиска построй то что советуют, какое-нибудь бинарное дерево, одновременно с массивом, тогда по дереву делай поиск, и после правок в массиве соответствующий узел дерева нужно будет перестроить чтобы отобразить изменения. Если повезёт, то получится существенная экономия на поиске.

#10
11:45, 25 авг. 2009

я вот думаю бинарную кучу сделать....но вот проблема....в определении кучи сказано....что свойства построенной кучи сохраняются только для всего массива(если она на нем построена)....но не для какого-либо подмассива.....
А значит после удаления элемента мне придется перестроить всю кучу...за n/2*log n.....а общая сложность будет такой...
400 000/2*log(400 000) + 399 999/2*log(399 999) + 399 998/2*log(399 998) + ... + 5/2*log(5)....по моему...это очень много...от того и бьют сомнения....

#11
11:54, 25 авг. 2009

Тогда можно предложить выложить цель алгоритма, чтобы предложили другой алгоритм. :)

#12
12:07, 25 авг. 2009

ZiV
> Megabyte-Ceercop
>
> уточни пожалуйста....
>
> Вот как я понял твои слова.....
> выбираю 4 наименьших эл из 400 000,


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

#13
12:10, 25 авг. 2009

мне наибольшие не нужны, нужны наименьшие....

#14
12:11, 25 авг. 2009

Megabyte-Ceercop
Нет, не прйдет. Он на каждом шаге меняет какой-то ключ по неизвестному нам признаку. Нелзя сказать, какие будут наибольшими в самом конце.

Страницы: 1 2 3 Следующая »
ПрограммированиеФорумОбщее

Тема в архиве.