#algorithm #data-structures
#алгоритм #структуры данных
Вопрос:
Сервер должен поддерживать данные за последние n дней. Сначала он должен показывать наиболее посещаемые страницы текущего дня, а затем наиболее посещаемые страницы следующего дня и так далее.
Я думаю о хэш-карте хэш-карт. Есть какие — нибудь предложения ?
Ответ №1:
Внешняя хэш-карта с ключом типа date и значением типа hash map.
Внутренняя хэш-карта с ключом типа string, содержащим URL, и значением типа int, содержащим количество посещений.
Пример на C#:
// Outer hash map
var visitsByDay =
new Dictionary<DateTime, VisitsByUrl>(currentDate, new VisitsByUrl());
...
// inner hash map
public class VisitsByUrl
{
public Dictionary<string, int> Urls { get; set; }
public VisitsByUrl()
{
Urls = new Dictionary<string, int>();
}
public void Add(string url)
{
if (Urls[url] != null)
Urls[url] = 1;
else
Urls.Add(url, 1);
}
}
Комментарии:
1. Я тоже думал в том же направлении. Это звучит как эффективное решение. Спасибо за вашу помощь!
2. это опровергает ожидания Картика без какого-либо учета его заявленных функциональных требований — есть только одно, и не очень реалистичное, но: «Сначала он должен показывать наиболее посещаемые страницы текущего дня, а затем наиболее посещаемые страницы следующего дня и так далее». Хэш-карты не отсортированы, а ваши привязаны к URL-адресу — как вы собираетесь находить наиболее посещаемую страницу? Итерация методом перебора, которая для хэш-карты обычно выполняется медленнее, чем векторная итерация. Хэш-карты позволяют быстро обновлять внутри дня, но зачем использовать внешнюю хэш-карту, когда массив / вектор из N лучше уплотняется и быстрее?
3. @Tony: Я не говорил, что это единственное решение. Это может быть недостаточно сложным для разработчика, склонного к перфекционизму. В любом случае, спасибо за отрицательный отзыв.
Ответ №2:
Вы можете сохранить хэш для каждого дня, который будет иметь тип :-
И очередь длиной n. в которой будут эти хэши за каждый день. Также вы будете хранить отдельные итоговые хэши, которые будут суммировать все эти
Class Stats {
queue< hash<url,hits> > completeStats;
hash<url,hits> totalStats;
public:-
int getNoOfTodayHits(url) {
return completeStats[n-1][url];
}
int getTotalStats(url) {
return totalStats[url];
}
void addAnotherDay() {
// before popping check if the length is n or not :)
hash<url,hits> lastStats = completeStats.pop();
hash<url,hits> todayStats;
completeStats.push_back(todayStats);
// traverse through lastStats and decrease the value from total stats;
}
// etc.
};
Комментарии:
1. Интересное решение, очень приятное. Спасибо. Вы решили использовать очередь хэш-таблиц вместо хэша хэша. По какой-либо конкретной причине вы выбрали это?? Я бы предположил, что вам придется сканировать всю очередь при поиске статистики с указанием даты. Каков ход ваших мыслей?
2. Мне не нужно обрабатывать даты для ключей в хэше 🙂 Работает Pop Push: P
Ответ №3:
У нас может быть комбинация стека и хэш-карты.
Мы можем создать объект с URL и меткой времени, затем поместить его в стек. Самый последний посещенный URL будет вверху.
Мы можем использовать временную метку в сочетании с URL-адресом для создания ключа, который сопоставляется с количеством посещенных URL-адресов.
Чтобы отобразить наиболее посещенные страницы в хронологическом порядке, мы можем открыть стек, создать ключ и получить количество, связанное с URL. Сортируйте их при отображении.
Временная сложность: O (n) время сортировки (зависит от количества посещенных страниц)
Ответ №4:
Это зависит от того, что вы хотите. Например, вы хотите сохранить фактические данные для страниц в истории или только URL-адреса? Если кто-то посетил страницу дважды, должна ли она дважды отображаться в истории?
Хэш-карта подошла бы, если вы хотите сохранить данные для страницы и хотите, чтобы каждая страница отображалась только один раз.
Если, как я считаю более вероятным, вы хотите сохранить только URL-адреса, но хотите, чтобы каждый сохранялся несколько раз, если его посещали более одного раза, массив / вектор, вероятно, имел бы больше смысла. Если вы ожидаете увидеть большое дублирование (относительно) длинных URL-адресов, вы могли бы создать набор URL-адресов и для каждого посещения сохранять какой-либо указатель / индекс / ссылку на рассматриваемый URL. Обратите внимание, однако, что поддержание этого может стать несколько нетривиальным.