Как сделать InsertionSort быстрее? - PullRequest
Новая
       7

Как сделать InsertionSort быстрее?

0 голосов
/ 15 октября 2018

Итак, у меня есть этот код 

   class Child{
    public:
        string code;
        float avg;
        unsigned int distance;
        int month;
        bool isSmallerThan(Child child, char *ordering_chars);
    };

    bool Child::isSmallerThan(Child child, char *ordering_chars) {
        for(int i=0; i<3; i++){
            if(ordering_chars[i] == 'a'){
                if(avg == child.avg)
                    continue;
                return avg < child.avg;
            }
            else if(ordering_chars[i] == 'd'){
                if(distance == child.distance)
                    continue;
                return distance < child.distance;
            }
            else if(ordering_chars[i] == 'm'){
                if(month == child.month)
                    continue;
                return month < child.month;
            }
        }
        return false;
    }

    void InsertionSort(Child *array, int n, char *ordering_chars){

        Child temp;
        int i, j;
        for(j = 1; j < n; j++)
        {
            temp = array[j];
            for(i = j - 1; (i >= 0) && array[i].isSmallerThan(temp, ordering); i--)
            {
                array[i+1] = array[i];
            }
            array[i+1] = temp;
        }
    }

У меня есть массив дочерних объектов, и я хочу отсортировать его по разным полям, в зависимости от массива ordering_chars, который взят из stdin.Например, если ordering_chars равен ['a', 'd', 'm'], это означает, что если avg равно, чем сортировать его по расстоянию, если оно тоже равно, чем сортировать по месяцам.Код работает, но он замедляется с большими данными.У вас есть какие-то решения, чтобы сделать эту работу более эффективной?Я думал об использовании указателей на функции, но я не уверен, как именно это сделать.

PS.Я должен использовать InsertionSort, это не может быть каким-либо другим способом сортировки, также я не могу использовать STL, потому что этот код предназначен для использования в Online Judge (я не участвую в каких-либо соревнованиях,просто сделай это, чтобы проверить себя и чему-то научиться).

Ответы [ 2 ]

0 голосов
/ 15 октября 2018

Вы можете избежать множества маленьких свопов, выполнив только один, в самом конце, как только найдете правильную позицию для предмета.В коде (будьте осторожны, не тестировались - отдельные ошибки могут скрываться незамеченными), 

for(int j = 1; j < n; j++) {
   Child temp = array[j];
   int swaps = 0;
   for(int i = j-1; (i >= 0) && array[i].isSmallerThan(temp, ordering); i--) {
      swaps ++;
   }
   if (swaps) {
        // make space & place new element where it belongs
        // beware: this may be problematic for more complex classes
        memmove(array+i+2, array+i+1, swaps);
        array[i+1] = temp;
   }
}

Другой источник экономии был бы за счет более быстрой функции сравнения.См. ответ Боба для возможной реализации.Без использования лямбды я бы пошел на 

bool Child::isSmallerThan(const Child &o, char *ordering_chars) const {
    int m = month == o.month ? 0 : month < o.month ? 1 : -1;
    int d = distance == o.distance ? 0 : distance < o.distance ? 1 : -1;
    int a = avg == o.avg ? 0 : avg < o.avg ? 1 : -1;

    switch (ordering_chars[0]) {
      case 'a': a <<= 2; break;
      case 'd': d <<= 2; break;
      case 'm': m <<= 2; break;
    }
    switch (ordering_chars[1]) {
      case 'a': a <<= 1; break;
      case 'd': d <<= 1; break;
      case 'm': m <<= 1; break;
    }

    return a+d+m > 0;
}
0 голосов
/ 15 октября 2018

Это слишком медленно, потому что вы делаете много копий для ваших дочерних переменных.

измените Child::isSmallerThan, чтобы взять Child & по ссылке, а не по значению.а также поменяй ребенка на тмп.Поместите это в цикл и измените также ссылку.

Также, как вы предложили, вы можете оптимизировать функцию сравнения.Сделайте 3 лямбда по одному для каждого последнего случая, которые возвращают int -1, 0, 1 для меньшего, равного или большего: 

auto get_comparator(char c) {
  if (c == 'a')
   return +[] (Child& x, Child& y) { /* compare x.avg and y.avg */ }
  if (c == 'd') 
   return +[] (Child& x, Child& y) { ... }
  if (c == 'm')
   return +[] (Child& x, Child& y) { ... }
}

внутри вашей InsertionSort, вы можете создать свою функцию сравнения: 

auto comp_first = get_comparator(ordering_chart[0]);
auto comp_second = get_comparator(ordering_chart[1]);
auto comp_second = get_comparator(ordering_chart[2]);

auto comparator = [comp_first, comp_second, comp_second](Child& x, Child& y) {
  int rez = comp_first(x, y);
  if (rez != 0) return rez == 1;
  rez = comp_second(x, y);
  if (rez != 0) return rez == 1;
  rez = comp_third(x, y);
  return rez == 1;
}

и используйте это, чтобы сравнить Детей

...