Отправлено SM 08 февраля 2006 г. 12:05 В ответ на: Можно ли каким-нибудь способом вычислить медиану пачки данных без сортировки? отправлено subver 08 февраля 2006 г. 10:33

1) Хорошую скорость дает QuickSelect, см. туда http://ndevilla.free.fr/median/median.pdf

2) Если данные приходят по одному, и надо делать "скользящую медиану", то держите связанный список двунаправленный плюс циркулярный буфер. Связанный список изначально и всегда сортирован, новое данное втыкаете сразу в его место. Ищете результат в том же проходе, что и данное втыкаете. А циркулярный буфер служит для запоминания ссылки на все элементы списка в порядке их поступления, чтобы быстро выкинуть из списка самый старый элемент, которому на пенсию пора. Я тут про енто уже писал.

• Ответ: в принципе можно и над блочными данными такую операцию проделать (со связанным списком), но что-то мне подсказывает, что такой фокус отъест солидный кусок памяти :) — subver   (08.02.2006 13:10 195.162.33.1, пустое)
  • Над блочными данными это конечно можно проделать, но ради чего? Чтобы все затормозить? Для блочных это не эффективно. А память она такая, бывает и нужна. — SM   (08.02.2006 13:39 213.141.159.26, пустое)
• Вот, как пить дать, видел я алгоритм поиска медианы, у которого скорость сходимости c*N, где N - число элементов массива (т.е. линейная). Помню, что эффективен этот алгоритм только тогда, когда N о-очень большое. — homekvn   (08.02.2006 12:10 212.185.161.237, пустое)

E-mail: info@telesys.ru