Сравнить 2 неупорядоченных набора записей в памяти

Ответ 1

Ваше второе решение похоже на попытку заново изобрести External merge sort. Это действительный подход, если ваши данные не вписываются в память, но это слишком сложно, когда ваши данные вписываются в память.

24 миллиона строк с двумя номерами каждый (8 байт) составляют всего ~ 200 МБ памяти. Два набора данных - 400 МБ. Это ничего не стоит на современном настольном оборудовании.

Загрузите оба набора данных в память. В простых массивах. Сортировка массивов в памяти. Найдите разницу, сканируя одновременно отсортированные массивы. Для этого вам не нужен фантастический LINQ.

Вот псевдокод. Мы имеем Array1 и Array2. Поддерживайте две переменные, которые содержат текущий индекс каждого массива: Idx1 и Idx2. Переместите индексы вдоль массивов, ища места, где LinkedColumn соответствует.

Idx1 = 0; Idx2 = 0;
while (true)
{
    // scan arrays until both indexes point to the same LinkedColumn
    // here we assume that both arrays are sorted by LinkedColumn
    // and that values in LinkedColumn are unique

    while (Idx1 < Array1.Length && Idx2 < Array2.Length &&
        Array1[Idx1].LinkedColumn < Array2[Idx2].LinkedColumn)
    {
        // move along Array1
        Idx1++;
    }

    while (Idx1 < Array1.Length && Idx2 < Array2.Length &&
        Array1[Idx1].LinkedColumn > Array2[Idx2].LinkedColumn)
    {
        // move along Array2
        Idx2++;
    }

    // at this point both indexes point to the same LinkedColumn
    // or one or both of the arrays are over

    if (Idx1 >= Array1.Length || Idx2 >= Array2.Length)
    {
        break;
    }

    // compare the values
    if (Array1[Idx1].CompareColumn != Array2[Idx2].CompareColumn)
    {
        // TODO: output/save/print the difference
    }

    Idx1++; Idx2++;
}

ИЛИ

вы можете сбросить оба набора данных в базе данных по вашему выбору в двух таблицах T1 и T2, создать уникальный индекс в LinkedColumn в обеих таблицах и запустить этот запрос:

SELECT
     T1.LinkedColumn  AS SrcLinkedColumn
    ,T1.CompareColumn AS SrcCompareColumn
    ,T2.LinkedColumn  AS DstLinkedColumn
    ,T2.CompareColumn AS DstCompareColumn
FROM
    T1 INNER JOIN T2 ON T1.LinkedColumn = T2.LinkedColumn
WHERE
    T1.CompareColumn <> T2.CompareColumn
ORDER BY
    T1.LinkedColumn
;

Псевдокод выше выполняет то же самое объединение, что и сервер СУБД для этого запроса.

Ответ 2

Если я правильно понял, вы получаете данные таблиц в C# по некоторым типам, например DataReader. Если вы храните записи, которые извлекаются из веб-службы, а затем выполняете некоторые запросы, как упоминал @VladimirBaranov, для хранения требуется слишком долгое время, и это не разумно.

Я думаю, что лучшим решением для сравнения в этом случае является Двоичный поиск. Его порядок времени O(log n), а порядок памяти - O (1). Таким образом, это не требует дополнительной памяти.

Вы можете использовать двоичный поиск, как показано ниже:

1- Сортировка таблицы меньшего размера.

Порядок времени: если эта таблица имеет n элементов, в среднем время выполнения O(nlogn) (дополнительная информация).

Порядок памяти: O (1), потому что метод sort в С# На месте.

2- Сравнение других табличных записей с отсортированной таблицей с помощью двоичного поиска.

Порядок времени: если в другой таблице есть m записей, время выполнения O(m)*O(logn) = O(mlogn). (дополнительная информация)

Порядок памяти: ему не нужна дополнительная память.

В заключение я благодарю, что это лучшее решение для вашей проблемы, но я думаю, что это решение является хорошим решением, которое имеет O(mlogn) время выполнения, O(1) порядок памяти и реализуется только на С#, нет необходимости сохранять записи в база данных.

Ответ 3

Вероятно, вы потеряете память из-за фрагментации памяти.

• Убедитесь, что вы используете эффективный способ чтения данных, таких как DataReader.
• Чтобы избежать фрагментации, получите счетчик ваших записей и инициализируйте массив List 1 с этим счетчиком перед началом вставки в массив. Если вы не можете получить счет, вы можете увеличить коэффициент роста вашего списка или построить запрос, который будет содержать исходный запрос в качестве суб-запроса, например: SELECT COUNT (*) FROM ([ВАШ ОРИГИНАЛЬНЫЙ ВОПРОС ЗДЕСЬ])
• Создайте массив struct, который содержит ваши поля или массив 2 измерений, для каждой строки не потребуется ссылка.
• Кроме того, вы можете сохранить исходные данные (список 1) в формате назначения. Таким образом, у вас будет только один массив в памяти.

Вот псевдокод:

• Получить количество строк списка List1:
• Создайте массив с двумя размерами для хранения данных из списка1
• Получить данные из списка 1 и добавить эти записи в ваш массив
• Утилизируйте первый datareader
• Используйте сортировку по месту для сортировки данных list1 (таким образом вы сможете использовать двоичный поиск, чтобы найти строку list1).
• Получить данные из списка2
• В строке списка List2 используется двоичный поиск для поиска соответствующей записи в списке1: добавьте значение сравнения List2 в соответствующую строку (помните, что в вашем массиве уже есть ваши 3 столбца). Вам нужно только установить значение сравнения list2).
• Очистите результат, удалив строки, которые не совпадают. Я рекомендую вам очистить, используя тот же массив. С помощью двух индексов вы можете сканировать массив и перемещать запись в массиве.

Ответ 4

Извините, но я могу только дать вам идею:

Ограничения:

• У цели есть миллионы записей.
• Источник имеет миллионы записей
• Ограниченная память

Идея:

• Используйте как минимум 2 машины для этого
• Один как [Source], а другой - как [Target], который имеет соответствующую службу
• Отправляйте все записи n (chunk) с [Source] на [Target], вызывая службу, позволяя ей соответствовать записям и затем отправлять результат в [Source]

Бонус:

4. Используйте более 1 машины [Target], и пусть машина [Source] использует их все в асинхронном сценарии и балансировке нагрузки.

Есть несколько похожих (или заранее) решений, которые вы можете найти, например:

• [Target] и [Source] могут использовать общую память (кэш-сервер, например), чтобы сохранить результат
• с использованием реального уровня балансировки нагрузки между ними для обработки нескольких запросов на несколько машин [Target]
• с использованием уровня очереди/обмена сообщениями
• даже используя несколько [Source] с несколькими компьютерами [Target]

Извините, но (по крайней мере, для меня) этот случай слишком велик, если использовать только 1 машину

Надеюсь, по крайней мере, это может дать вам идею

Ответ 5

Похоже, что LinkedColumn содержит уникальные значения для каждого источника, я бы загружал обе данные в две таблицы в локальной базе данных, создавал индекс на LinkedColumn и делал соединение.

Или вы можете загрузить обе данные в простой файл, включая исходный идентификатор в каждой строке, следующим образом (не включать заголовок):

LinkedColumn   Identifier   CompareColumn
1              S            100
2              S            200
3              S            300
                   ...
4              O            70
3              O            80
2              O            90

S означает SQL Server и O для Oracle. Сортировка файла (возможно, вы можете запустить сортировку ОС или другую внешнюю сортировку). Прочитайте отсортированный файл по строкам. Первая строка должна быть сохранена, поэтому вы сравните ее LinkedColumn со второй строкой для сопоставления, тем самым собирая их или сохраняя вторую и отбрасывая первую, чтобы найти соответствие на третьем и т.д.

Надеюсь, что это поможет.

Ответ 6

Как насчет удаления элементов, которые соответствуют? Что-то вроде:

List1.RemoveAll(x => List2.Any(y => y.LinkedColumn == x.LinkedColumn && y.CompareColumn == x.CompareColumn))

Ответ 7

Просто оставьте это задание SQL Server.

Пусть он обрабатывает WHERE CLAUSE

T1.CompareColumn <> T2.CompareColumn