Кстати предположив что у каждого примерно по 100-200 друзей и с каждым из них от 10 до 50 общих друзей можно оценить диаметр нашего графа… Только, извините, мне лень)))
Поиск пути на невзвешанном графе в 20млн вершин эт простой поиск волной:
N вершин (N < 20 млн. — допустим у нас стока народу вконтакте)
Есть очередь вершин в которые мы собираемся идти и массив из N элементов где отмечаем в каких вершинах были. Изначально массив забит нулями, единицей отмечена только начальная вершина, а в очереди только начальная вершина.
На каждом шаге берем одну вершину из очереди, добавляем ее детей в которых еще небыли и пишем единички в элементах массива им соответствующих. Заодно сравниваем с номером конечной вершины. Можем в массив вместо единичек писать расстояние до начальной (что обычно и делается). Можно в дополнительный массив писать данные для трассировки — номер вершины из которой мы пришли.
Массив из 20млн. байт — 20 МБ. Очередь (каждая вершина побывает в очереди <= 1 раза) <= 20Мб…
Гм… процессор допустим с частотой 3,2ГГц — 3 миллиарда операций в секунду… самые быстрые серверные жесткие диски не превосходят 1000IOPS… Такты процессора/IOPS винчестера = 3200000 тактов — столько процессор ждет результата операции с жестким диском…
SSD — 1 миллион IOPS в секунду… 3200 IOPS на 3000 тактов процессора это уже практически оперативка… единственное что ресурс пока что ограниченный...)
кстати ты слышал что-нибудь про то что винчестер читает не по 1му байту?...) про SSD не знаю правда…
Я своим 2480 не доволен — старая ALi web-camera сдохла (мало того что не поддерживается в V4L), HDD убитый умирает самопроизвольно периодически (винда как-то приспособилась рестартить его сразу, в Linux ждет минуту-другую) и куплено это в Эльдорадо черт знает зачем за такие деньги… Подарок блин… Попробуй не смотри в зубы коню дареному если у него изо рта воняет больше чем из попы…
250 т.р. — средняя конфигурация топовой игровой тачки в магазинах которые +30%… Топовые игры в полном функционале идут только на таких… Хотя вообщем 8x2.83 туда не ставят, максимум 4x2.3… Главное — видео…
Девайс и правда не для гиков, согласен, по поводу шейдеров и встроенных интеловских видео карточек тоже… Но имхо 10 рублей за собранный ноут в магазине — не цена… Пусть даже ноут еле тянет на средненький офисный ПК — средненький офисный ПК с монитором кстати будет дороже стоить…
Может быть вы еще и с файлами работать одновременно пытаетесь? (копировать там например...) Виртуальная память не заканчивается? Или виста научилась себя сносить чтобы память освобождать?
на нашей кафедре были попытки организовать что-то подобное — студенты собирались в группы в лабораториях университета с целью изучения существующих технологий по нескольким направлениям… результат вполне приличный, 1й курс усвоил многие полезные вещи которые ориентированы на программу 4го-5го курса… к сожалению для исследовательских работ масштаб данной инициативы довольно маловат…
N вершин (N < 20 млн. — допустим у нас стока народу вконтакте)
Есть очередь вершин в которые мы собираемся идти и массив из N элементов где отмечаем в каких вершинах были. Изначально массив забит нулями, единицей отмечена только начальная вершина, а в очереди только начальная вершина.
На каждом шаге берем одну вершину из очереди, добавляем ее детей в которых еще небыли и пишем единички в элементах массива им соответствующих. Заодно сравниваем с номером конечной вершины. Можем в массив вместо единичек писать расстояние до начальной (что обычно и делается). Можно в дополнительный массив писать данные для трассировки — номер вершины из которой мы пришли.
Массив из 20млн. байт — 20 МБ. Очередь (каждая вершина побывает в очереди <= 1 раза) <= 20Мб…
Помоему работает за t(N)…
Собственно всё…
SSD — 1 миллион IOPS в секунду… 3200 IOPS на 3000 тактов процессора это уже практически оперативка… единственное что ресурс пока что ограниченный...)
кстати ты слышал что-нибудь про то что винчестер читает не по 1му байту?...) про SSD не знаю правда…
Хотя про жалобы вру — у всех них виста стоит…
welcome!