ReSQL.ru
     
powered by simpleCommunicator - 2.0.61     © 2026 Programmizd 02
Мобильная версия    Контакт    Правила    FAQ    Помощь
Целевая тема:
Создать новую тему:
Автор:
Закрыть
Цитировать
Доб. в избранное | Игнор. тему | Прикреп. тему | Пометить прочит. / непрочит. | Фильтр
Форумы / Программирование [игнор отключен] [закрыт для гостей] / Алгоритмы для бесконечного потока данных.
25 сообщений из 39, страница 1 из 2
  1  все
Алгоритмы для бесконечного потока данных.
    #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
| Ответить | Цитировать | Написать  
25 сообщений из 39, страница 1 из 2
  1  все
Форумы / Программирование [игнор отключен] [закрыт для гостей] / Алгоритмы для бесконечного потока данных.
Найденые пользователи ...
Разблокировать пользователей ...
Читали тему (0):
Читали форум (0):
Пользователи онлайн (0):
Польз. соглашение   Полит. конфиден.  
NoSQL.ru       Кролег: Проекты, Новости, Чат       РЕД ФОРУМ       Фотоальбом: Участники, Встречи
Закрыть
start [/forum/topic.php?fid=16&msg=38750572&tid=1341222]:
 0ms
get settings:
 8ms
get forum list:
 19ms
check forum access:
 3ms
check topic access:
 3ms
track hit:
 152ms
get topic data:
 8ms
get forum data:
 2ms
get page messages:
 73ms
get tp. blocked users:
 2ms
others: 229ms
total:  499ms
созд. / загр.: 499ms
x
x
Закрыть


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