Эффективная работа с большими объемами данных

#алгоритм #big_data

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

Есть ли какой-нибудь эффективный метод (из области big-data) выделения из этого массива
данных групп сущностей, состоящих из одних и тех же символов (так называемых анаграмм)?
    

Ответы

Ответ 1

Стандартная идея вот какая:


К каждой сущности дописать её номер в исходном списке.
У каждой сущности отсортировать символы.
Отсортировать сущности. Теперь анаграммы будут находиться рядом.
Теперь для нахождения анаграмм нужен лишь один пробег по данным.


Все эти операции хорошо «параллелятся», Кроме, пожалуй сортировки.

С учётом этого можно изменить немного алгоритм:


Распартиционировать данные как угодно.
Пронумеровать сущности и отсортировать их символы на каждом хосте по отдельности
(номеру назначать уникальный префикс, чтобы не смешивать)
Отсортировать данные каждого хоста.
Смёржить все данные. Сначала заливать результат на первый хост, когда 1/n всех данных
зальётся — на второй хост и т. д. (Это по сути перепартиционирование.)
Далее пробег по данным на каждом хосте.


Вместо пункта 4, возможно, более эффективно будет не сливать данные вместе, а делать
многохостовый пробег:

string currentValue = null;
int anagramCount = 0;
string[] nextByHost = new string[N];
for (i = 0..n-1) { currentByHost[i] = ""; nextByHost = fetch from host[i]; }

while (any of hosts has data)
{
    if any of nextByHost[i] equals to currentValue,
        anagramCount++
        fetch next from host[i] to nextByHost[i]
    else
        store currentValue and anagramCount
        currentValue = min(nextByHost)
}