Объединение двух массивов класса

Question

У меня есть два массива класса Record.Класс Record определяется следующим образом:

class Record{
char* string; //the word string
int count; //frequency word appears
}

. Эти два массива определены (уже инициализированы)

Record recordarray1=new Record[9000000];  //contains 9000000 unsorted Records
Record recordarray2=new Record[8000000]  //contains 8000000 unsorted Records

. Цель состоит в том, чтобы найти строки, которые совпадают между двумя массивами идобавьте их в новый массив, где их счетчики суммируются, и если в другом массиве есть строка, которой нет, просто добавьте в новый массив.Чтобы сделать это, я попытался сначала отсортировать два массива (в алфавитном порядке по строкам), затем сравнить recordarray2, если строка совпадает, то продвинуть индекс recordarray2, в противном случае продвинуть индекс recordarray1, пока вы не найдете один,Если вы не нашли его, добавьте его в новый массив.

К сожалению, этот метод СЛИШКОМ слишком медленный, сама сортировка занимает 20+ секунд с сортировкой STL.Есть ли более быстрый метод сортировки, который мне не хватает?

Answer 1

Я чувствую, что сортировка не нужна. Вы можете использовать следующий алгоритм.

1. Начните с первого элемента recordarray1; положить в новый массив
2. Поиск элементов в recordarray2. Если элемент найден, приращение count в новом массиве. Также установите recordarray2[N]::count до отрицательного значения; так что он не будет проверен снова на шаге 3
3. Поместите все элементы из recordarray2 который не имеет отсчет установлен в отрицательный в новый массив. Если отрицательный count столкнулся, то просто измените его положительны.

Примечание: этот алгоритм не заботится, если у вас есть одинаковые строковые элементы в одном массиве. Также не используйте string в качестве имени переменной. Так же это имя типа std::string.

Answer 2

Сортировка объекта может быть дорогой, поэтому я постараюсь избежать этого.

Одним из более быстрых способов может быть создание индекса для каждого массива с использованием std :: hash_map со строкой as, имеющей index, и индексом массива в качестве значения. Вы получаете два контейнера, которые можно повторять одновременно. Итератор для меньшего будет продвигаться до тех пор, пока вы не найдете совпадение или другие точки на меньшее значение. Это приведет вас к предсказуемому количеству итераций.

Answer 3

Возможное решение - использовать unordered_map. Алгоритм должен быть следующим:

Put the first array into the map, using strings as keys and count as values. 
For each member in the second array, check it against containment in the map.
    If it exists there
        Put the record into the new array, combining counts
        Remove the record from the map
    Else
        Put the record into the new array
Iterate throug the remaining recors in the map and put the in to the new array.

Сложность этого алгоритма составляет приблизительно O (n + m)

Answer 4

Если я правильно понял, ваш алгоритм должен взять O( nlogn + mlogm [отсортировать оба массива] + n + m [просмотреть массивы и сравнить] ).
Это может быть не слишком оптимизацией, но вы пытаетесь отсортировать только один из массивов и используете бинарный поиск, чтобы проверить, присутствуют или нет элементы другого массива. Так что теперь требуется O( n [скопировать один массив в качестве нового массива] + nlogn [чтобы отсортировать его] + mlogn [для двоичного поиска элементов второго в отсортированном новом] ).

НТН