ReSQL.ru
     
powered by simpleCommunicator - 2.0.61     © 2026 Programmizd 02
Мобильная версия    Контакт    Правила    FAQ    Помощь
Целевая тема:
Создать новую тему:
Автор:
Закрыть
Цитировать
Доб. в избранное | Игнор. тему | Прикреп. тему | Пометить прочит. / непрочит. | Фильтр
Форумы / Программирование [игнор отключен] [закрыт для гостей] / Алгоритмы для бесконечного потока данных.
39 сообщений из 39, показаны все 2 страниц
  все  
Алгоритмы для бесконечного потока данных.
    #38750500
eldarkaa
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
eldarkaa
Участник
Добрый день, господа программисты.
Представьте себе, что есть модуль, на вход которому бесконечно поступают ID пользователей. В любой момент времени м одуль должен уметь быстро ответить сколько за всё время накопилось уникальных пользователей . Каким образом Вы бы стали решать задачу при условии, что:
1) нужно получить точное количество уникальных пользователей
2) достаточно примерного значения с погрешностью, не превышающей нескольких процентов
--
Мое видение: Главное и ключевое слово "бесконечно". Это означает, что мы не можем хранить все записи.
Если бы мы могли хранить все записи, то для первого пункта можно было бы создать Map из уникальных ID и потом брать его "длину".
Но опять же это неправильно, если рассматривать бесконечный поток данных.
Ваши идеи?
...
Рейтинг: 0 / 0
18.09.2014, 14:50
| Ответить | Цитировать | Написать  
Алгоритмы для бесконечного потока данных.
    #38750513
Leonid Kudryavtsev
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Leonid Kudryavtsev
Участник
Межгалактическую систему идентификации планируете?

ВикиНаселение земли
1 ноября 2011 — 7,0 млрд человек
...
Рейтинг: 0 / 0
18.09.2014, 15:01
| Ответить | Цитировать | Написать  
Алгоритмы для бесконечного потока данных.
    #38750521
Dima T
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Dima T
Участник
Зачем мап? Возьми полноценный SQL-сервер и пиши туда все входящие ID и время поступления. Получишь таблицу с логом, а дальше хоть какие выборки делай.
...
Рейтинг: 0 / 0
18.09.2014, 15:05
| Ответить | Цитировать | Написать  
Алгоритмы для бесконечного потока данных.
    #38750525
Leonid Kudryavtsev
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Leonid Kudryavtsev
Участник
Для бесконечного потока не поможет, жесткие диски конечны.

Другое дело, если на магнитной ленте - тогда подклеивать можно, скотчем. Главное, что бы атомы железа для феромагнитного покрытия во вселенной раньше не закончились. Как я понимаю, атомов железа не так уж и много, с точки зрения бесконечности...
...
Рейтинг: 0 / 0
18.09.2014, 15:08
| Ответить | Цитировать | Написать  
Алгоритмы для бесконечного потока данных.
    #38750545
eldarkaa
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
eldarkaa
Участник
хорошо троллите, но нужна помощь
Считайте, что у меня сервер на Пентиум4 с жестким диском на 128Мб. И забудьте про БД, в данной задаче речь идет о Структурах Данных.
...
Рейтинг: 0 / 0
18.09.2014, 15:21
| Ответить | Цитировать | Написать  
Алгоритмы для бесконечного потока данных.
    #38750551
Dima T
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Dima T
Участник
Пофиг какой у тебя сервер. Планируемые характеристики задачи надо конкретнее задавать. Какой тип и размер у ID? На какое число уникальных пользователей примерно рассчитывать?
...
Рейтинг: 0 / 0
18.09.2014, 15:25
| Ответить | Цитировать | Написать  
Алгоритмы для бесконечного потока данных.
    #38750558
eldarkaa
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
eldarkaa
Участник
ID : String
Количество: население Земли х10 (по 10 аккаунтов). Чтобы отпало желание хранить их всех в БД и проверять на наличие повторения (уникальность).
...
Рейтинг: 0 / 0
18.09.2014, 15:31
| Ответить | Цитировать | Написать  
Алгоритмы для бесконечного потока данных.
    #38750561
Leonid Kudryavtsev
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Leonid Kudryavtsev
Участник
у тебя уже отпало?
...
Рейтинг: 0 / 0
18.09.2014, 15:32
| Ответить | Цитировать | Написать  
Алгоритмы для бесконечного потока данных.
    #38750565
eldarkaa
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
eldarkaa
Участник
Leonid Kudryavtsev,

Я разрешаю вам больше не писать в данном топике. Спасибо.
...
Рейтинг: 0 / 0
18.09.2014, 15:36
| Ответить | Цитировать | Написать  
Алгоритмы для бесконечного потока данных.
    #38750572
Фотография Яростный Меч
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Яростный Меч
Участник
если нет возможности хранить map уникальных id (их слишком много), то никак.
вот поступает на вход новое id - как проверить, что оно уже было?

но сдается мне, 70 миллиардов строк хранить таки можно.
...
Рейтинг: 0 / 0
18.09.2014, 15:42
| Ответить | Цитировать | Написать  
Алгоритмы для бесконечного потока данных.
    #38750586
Dima T
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Dima T
Участник
В целом задача сводится к тому что надо проверить было ли такое значение ID, это не реализовать без хранения факта что оно было. Т.е. минимум места 1 бит на один ID. Или 8 ID в одном байте. Это идеал, в реале будут издержки на организацию хранения, думаю можно вписаться в 2-4 ID на один байт.
...
Рейтинг: 0 / 0
18.09.2014, 15:48
| Ответить | Цитировать | Написать  
Алгоритмы для бесконечного потока данных.
    #38750588
Фотография Яростный Меч
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Яростный Меч
Участник
Dima TТ.е. минимум места 1 бит на один IDтам id - строки
...
Рейтинг: 0 / 0
18.09.2014, 15:50
| Ответить | Цитировать | Написать  
Алгоритмы для бесконечного потока данных.
    #38750632
Dima T
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Dima T
Участник
Яростный МечDima TТ.е. минимум места 1 бит на один IDтам id - строки
можно к числам свести, например посчитать CRC37, что сделает из строки 37-битное число с заданной погрешностью 1-2%
Если изначально на такой размер рассчитывать и не заморачиваться что возможно их намного меньше, то надо кусок памяти 2^29 байт = 0,5 Гб.
...
Рейтинг: 0 / 0
18.09.2014, 16:07
| Ответить | Цитировать | Написать  
Алгоритмы для бесконечного потока данных.
    #38750682
Dima T
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Dima T
Участник
Меня другое интересует, как эти 70 млрд. ID на сервер попадут? Допустим средний логин 15 байт, т.е. это 1 Тб трафика только на передачу логинов, а ведь еще и полезная инфа будет и ответ ... для обработки всего этого безобразия датацентр потребуется построить, так что жалкие 0,5 Гб памяти для подсчета там найдутся
...
Рейтинг: 0 / 0
18.09.2014, 16:34
| Ответить | Цитировать | Написать  
Алгоритмы для бесконечного потока данных.
    #38750709
Dima T
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Dima T
Участник
Занизил я 0,5 Гб, надо 16 Гб (2^34). Не суть, если гигантоманией не страдать и поставить нормальный предел в 8 млн. уникальных ID, то хватит массива в 1 Мб:
Считаешь CRC32 от ID (совпадать будет с погрешностью несколько %), оставляешь 23 бита: 20 номер элемента массива, 3 номер бита. Метишь бит в 1.
Для вывода результата считаешь биты установленные в 1.
Вместо CRC32 можно любой другой хэш взять (MD5 например), просто затестить какой быстрее считается.
...
Рейтинг: 0 / 0
18.09.2014, 16:50
| Ответить | Цитировать | Написать  
Алгоритмы для бесконечного потока данных.
    #38750845
BagaBaga
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
BagaBaga
Участник
eldarkaaхорошо троллите, но нужна помощь
Считайте, что у меня сервер на Пентиум4 с жестким диском на 128Мб . И забудьте про БД, в данной задаче речь идет о Структурах Данных.
На какой барахолке Вы такой достанете?
...
Рейтинг: 0 / 0
18.09.2014, 18:55
| Ответить | Цитировать | Написать  
Алгоритмы для бесконечного потока данных.
    #38750857
Basil A. Sidorov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Basil A. Sidorov
Участник
BagaBagaНа какой барахолке Вы такой достанете?Ни на какой. Не было таких дисков.
...
Рейтинг: 0 / 0
18.09.2014, 19:07
| Ответить | Цитировать | Написать  
Алгоритмы для бесконечного потока данных.
    #38750887
Dima T
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Dima T
Участник
Basil A. SidorovBagaBagaНа какой барахолке Вы такой достанете?Ни на какой. Не было таких дисков.
Было и даже меньше
...
Рейтинг: 0 / 0
18.09.2014, 19:36
| Ответить | Цитировать | Написать  
Алгоритмы для бесконечного потока данных.
    #38751087
Basil A. Sidorov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Basil A. Sidorov
Участник
Dima T Было и даже меньше Было 120Мб. 128 - не было.
...
Рейтинг: 0 / 0
19.09.2014, 04:29
| Ответить | Цитировать | Написать  
Алгоритмы для бесконечного потока данных.
    #38751291
Фотография MasterZiv
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
MasterZiv
Участник
eldarkaaМое видение: Главное и ключевое слово "бесконечно". Это означает, что мы не можем хранить все записи.


Твоё видение в корне неверно.
Потому что если брать это ограничение за основу, то решений у задачи нет.

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

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

Именно MAP из уникальных ID, и его длина.
MAP либо в памяти, либо на диске (и частично в памяти).
Либо распределённый.
...
Рейтинг: 0 / 0
19.09.2014, 11:18
| Ответить | Цитировать | Написать  
Алгоритмы для бесконечного потока данных.
    #38751292
Фотография MasterZiv
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
MasterZiv
Участник
eldarkaaхорошо троллите, но нужна помощь
Считайте, что у меня сервер на Пентиум4 с жестким диском на 128Мб. И забудьте про БД, в данной задаче речь идет о Структурах Данных.

БД -- это одна из структур данных.
...
Рейтинг: 0 / 0
19.09.2014, 11:19
| Ответить | Цитировать | Написать  
Алгоритмы для бесконечного потока данных.
    #38751294
Фотография MasterZiv
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
MasterZiv
Участник
eldarkaaID : String
Количество: население Земли х10 (по 10 аккаунтов). Чтобы отпало желание хранить их всех в БД и проверять на наличие повторения (уникальность).

Ну, я имел дело с БД такого размера (55 миллиардов записей). Вполне успешно работала на кластере из 8 машин. 32 гига памяти кажется в каждой, по 16 процов (кажется).

Но это не бесконечность.

Кстати, в ходе этого проекта я понял, насколько трудно найти сейчас реально большие данные.
...
Рейтинг: 0 / 0
19.09.2014, 11:22
| Ответить | Цитировать | Написать  
Алгоритмы для бесконечного потока данных.
    #38751297
Фотография MasterZiv
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
MasterZiv
Участник
MasterZiveldarkaaID : String
Количество: население Земли х10 (по 10 аккаунтов). Чтобы отпало желание хранить их всех в БД и проверять на наличие повторения (уникальность).

Ну, я имел дело с БД такого размера (55 миллиардов записей). Вполне успешно работала на кластере из 8 машин. 32 гига памяти кажется в каждой, по 16 процов (кажется).

Но это не бесконечность.

Кстати, в ходе этого проекта я понял, насколько трудно найти сейчас реально большие данные.

Да, в этой БД хранилось немного больше, чем просто ID для каждого.
...
Рейтинг: 0 / 0
19.09.2014, 11:23
| Ответить | Цитировать | Написать  
Алгоритмы для бесконечного потока данных.
    #38751298
Фотография MasterZiv
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
MasterZiv
Участник
MasterZivMasterZivпропущено...


Ну, я имел дело с БД такого размера (55 миллиардов записей). Вполне успешно работала на кластере из 8 машин. 32 гига памяти кажется в каждой, по 16 процов (кажется).

Но это не бесконечность.

Кстати, в ходе этого проекта я понял, насколько трудно найти сейчас реально большие данные.

Да, в этой БД хранилось немного больше, чем просто ID для каждого.

И запросы были много сложнее, чем поиск по ID.
...
Рейтинг: 0 / 0
19.09.2014, 11:24
| Ответить | Цитировать | Написать  
Алгоритмы для бесконечного потока данных.
    #38751300
Фотография MasterZiv
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
MasterZiv
Участник
Яростный Мечесли нет возможности хранить map уникальных id (их слишком много), то никак.
вот поступает на вход новое id - как проверить, что оно уже было?

но сдается мне, 70 миллиардов строк хранить таки можно.

70 не знаю, а вот 60 (~кол-во пальцев на руках у всех жителей земли) -- вполне.
...
Рейтинг: 0 / 0
19.09.2014, 11:25
| Ответить | Цитировать | Написать  
Алгоритмы для бесконечного потока данных.
    #38751412
Barlone
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Barlone
Участник
Dima TВместо CRC32 можно любой другой хэш взять (MD5 например), просто затестить какой быстрее считается.Ну глядя на алгоритмы, md5 должен быть примерно в 30 раз медленнее crc. Ну так то да, если допустима погрешность, то взять какой-нибудь хеш и хранить по биту на каждое его возможное значение - самый компактный способ хранения будет. Только размер хеша надо правильно выбрать. А то для crc32 больше четырех с небольшим миллиардов уникальных пользователей никак не получится :)
...
Рейтинг: 0 / 0
19.09.2014, 12:38
| Ответить | Цитировать | Написать  
Алгоритмы для бесконечного потока данных.
    #38751694
Leonid Kudryavtsev
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Leonid Kudryavtsev
Участник
Главное, не забывайте про зеленных человечков с Марса!!! Они тоже хотят, что бы их посчитали. CRC32 и придел в 4 млр. не катит

Да... и не забывайте требования к оборудованию... нужно все на 128 Mb диске сделать....
...
Рейтинг: 0 / 0
19.09.2014, 15:44
| Ответить | Цитировать | Написать  
Алгоритмы для бесконечного потока данных.
    #38751707
Dima T
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Dima T
Участник
Можно CRC64 взять и чтобы в 128 уложиться жать JPEG`ом раз небольшие потери разрешены
...
Рейтинг: 0 / 0
19.09.2014, 15:52
| Ответить | Цитировать | Написать  
Алгоритмы для бесконечного потока данных.
    #38751727
Фотография MasterZiv
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
MasterZiv
Участник
Ребята, какие такие хэши, все хэши теряют данные, уникальность после хэша не проверить.
...
Рейтинг: 0 / 0
19.09.2014, 16:08
| Ответить | Цитировать | Написать  
Алгоритмы для бесконечного потока данных.
    #38751741
Dima T
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Dima T
Участник
MasterZiv, ознакомься с ТЗ
eldarkaa2) достаточно примерного значения с погрешностью, не превышающей нескольких процентов

Осталось провести исследование сколько процентов теряют разные хэши, чтобы уложиться в заданные пределы.
...
Рейтинг: 0 / 0
19.09.2014, 16:16
| Ответить | Цитировать | Написать  
Алгоритмы для бесконечного потока данных.
    #38751756
Dima T
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Dima T
Участник
Я как-то такое исследование устраивал, надо было ускорить поиск по точному совпадению строки char(100) в таблице из полумиллиона уникальных записей. Оказалось CRC32 почти тянет на уникальный ключ, повторов было очень мало. Но если всегда считать CRC от 100 символов, а если обрезать конечные пробелы - количество повторов значительно увеличиваются.
...
Рейтинг: 0 / 0
19.09.2014, 16:26
| Ответить | Цитировать | Написать  
Алгоритмы для бесконечного потока данных.
    #38751765
miksoft
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
miksoft
Участник
Dima TMasterZiv, ознакомься с ТЗ
eldarkaa2) достаточно примерного значения с погрешностью, не превышающей нескольких процентов

Осталось провести исследование сколько процентов теряют разные хэши, чтобы уложиться в заданные пределы.Дело не в том, сколько теряют хэши, а в том, каково распределение входных данных.
Если, например, функия хэша дает одинаковое значение (т.е. коллизию) для четного N и для нечетного N+1, а во входном потоке четных чисел на порядок больше, чем нечетных, то погрешность составит десятки-сотни процентов, а вовсе не 1/N.
...
Рейтинг: 0 / 0
19.09.2014, 16:33
| Ответить | Цитировать | Написать  
Алгоритмы для бесконечного потока данных.
    #38751970
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
Фильтр Блума частично решает проблему существования ключа в бесконечной выборке
при условии конечной памяти самого фильтра. Но подсчёт (итератор) в нем невозможен.

Кроме того из постановки вопроса непонятно, были ли транзакции на удаление ключей.
Если нет - в большинстве случаев можно просто анализировать count(*) событий.
...
Рейтинг: 0 / 0
19.09.2014, 19:01
| Ответить | Цитировать | Написать  
Алгоритмы для бесконечного потока данных.
    #38752755
Фотография Виталий Гробштейн
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Виталий Гробштейн
Участник
eldarkaa,
Вам нужно просто осознать, что ничего бесконечного не бывает. Потом оценить разумно объем данных которые РЕАЛЬНО нужно хранить. Уверен, что ничего суперсложного в вашей задаче не останется.
...
Рейтинг: 0 / 0
21.09.2014, 01:43
| Ответить | Цитировать | Написать  
Алгоритмы для бесконечного потока данных.
    #38752803
scf
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
scf
Участник
Эту задачу решает вот такая штука:
http://ru.wikipedia.org/wiki/Фильтр_Блума

Только вам нужен Multiset, т.е. вместо битового массива нужен массив счетчиков.
...
Рейтинг: 0 / 0
21.09.2014, 08:25
| Ответить | Цитировать | Написать  
Алгоритмы для бесконечного потока данных.
    #38753160
Фотография SashaMercury
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
SashaMercury
Участник
MasterZivТвоё видение в корне неверно.
Потому что если брать это ограничение за основу, то решений у задачи нет.

Правильный ответ уже был. И на пункт а, и на пункт б.

Ваша задача(оба пункта) практически равносильна попытке найти сумму расходящегося ряда.
...
Рейтинг: 0 / 0
22.09.2014, 03:16
| Ответить | Цитировать | Написать  
Алгоритмы для бесконечного потока данных.
    #38753500
Фотография MasterZiv
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
MasterZiv
Участник
Dima TMasterZiv, ознакомься с ТЗ
eldarkaa2) достаточно примерного значения с погрешностью, не превышающей нескольких процентов

Осталось провести исследование сколько процентов теряют разные хэши, чтобы уложиться в заданные пределы.

Ну-ну, успехов ....
...
Рейтинг: 0 / 0
22.09.2014, 14:09
| Ответить | Цитировать | Написать  
Алгоритмы для бесконечного потока данных.
    #38753510
Dima T
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Dima T
Участник
MasterZivНу-ну, успехов ....

Успехи есть, выше писал, работает в реальном проекте. :)
...
Рейтинг: 0 / 0
22.09.2014, 14:16
| Ответить | Цитировать | Написать  
Алгоритмы для бесконечного потока данных.
    #38753551
Dima T
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Dima T
Участник
Глянул текущее состояние:
почти 495 тыс. уникальных записей, совпавших CRC32 - всего 29 штук
Если взять остаток деления CRC32 на 1 Мб - дублей 100 тыс.
2 мб - 54 тыс.
4 мб - 28 тыс.
8 мб - 14 тыс.
16 мб - 7 тыс.

Зависимость точности от объема просматривается.
...
Рейтинг: 0 / 0
22.09.2014, 14:44
| Ответить | Цитировать | Написать  
39 сообщений из 39, показаны все 2 страниц
  все  
Форумы / Программирование [игнор отключен] [закрыт для гостей] / Алгоритмы для бесконечного потока данных.
Найденые пользователи ...
Разблокировать пользователей ...
Читали тему (0):
Читали форум (0):
Пользователи онлайн (0):
Польз. соглашение   Полит. конфиден.  
NoSQL.ru       Кролег: Проекты, Новости, Чат       РЕД ФОРУМ       Фотоальбом: Участники, Встречи
Закрыть
start [/forum/topic.php?all=1&fid=16&tid=1341222]:
 0ms
get settings:
 6ms
get forum list:
 9ms
check forum access:
 3ms
check topic access:
 3ms
track hit:
 43ms
get topic data:
 7ms
get forum data:
 1ms
get page messages:
 41ms
get tp. blocked users:
 1ms
others: 201ms
total:  315ms
созд. / загр.: 315ms
x
x
Закрыть


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