Войти
ПрограммированиеФорумОбщее

Сортировка однонаправленного списка за O(N log N) без рекурсии (4 стр)

Страницы: 1 2 3 4 5 Следующая »
#45
(Правка: 23:20) 23:19, 11 июля 2019

1 frag / 2 deaths
> Не вижу никакого смысла отделять закрывашку от else
Некоторые считают, что не ставить закрывашку в однострочных бранчах вредно. Частенько программисты комментируют условия во время отладки и порой из-за невнимательности программа ведет себя совсем не так как ожидалось.

if (condition)
  // doSomething();
doSomethingMore(); // does this thing should be executed in any case?
Были бы скобки - сэкономилась бы пара часов при отладке. К вопросу о расстановке скобок можно подойти с той же позиции, если скобка проставлена на новой строке, то закомментировать условие - не проблема
//if (condition)
{
  doSomething();
}
а если скобка находится на той же строке что и условный оператор - то возникнет ошибка компиляции, причем при компиляции большого проекта обнаружить это можно спустя два часа, когда компилятор доберется до исходного файла с ошибкой.

#46
23:30, 11 июля 2019

MrShoor
> Да, но будет всё так же безнадежно медленнее кода из #28 поста.
Почему? Количество операций у них сравнимое будет.

#47
23:32, 11 июля 2019

MrShoor
> Добавил код в предыдущий пост
>Да, теперь понял что ты имел ввиду. Да, так будет лучше.
p.s. Единственно - ты помоему знак не в ту сторону тут поставил:
>if(GetPointsData(heads[idx])<=GetPointsData(heads[idx2])) break;
Я написал из расчета сверху - меньший

#48
(Правка: 23:46) 23:43, 11 июля 2019

}:+()___ [Smile]
> Почему? Количество операций у них сравнимое будет.
Стоимость константы при операции будет разное. Тут тот же случай, почему у суслика merge sort был медленнее insertion sort на малом количестве элементов.

Aslan
> Я написал из расчета сверху - меньший
Тогда тут вроде как надо знак поменять:
> idx2+=(idx2+1<N && GetPointsData(heads[idx2+1])<GetPointsData(heads[idx2]));
не?

upd. Не, не надо там знак менять, выражение же инверированное. Да, все правильно.

#49
1:51, 12 июля 2019

MrShoor
> Стоимость константы при операции будет разное.
Так я и спрашиваю, за счет чего? Оба алгоритма состоят почти целиком из compare и swap.
Единственно, когда простой линейный алгоритм может выиграть — это когда новый head всегда на месте.

#50
2:17, 12 июля 2019

}:+()___ [Smile]
> Так я и спрашиваю, за счет чего? Оба алгоритма состоят почти целиком из compare
> и swap.
2 compare на операцию у хипа.

#51
3:57, 12 июля 2019

MrShoor
> 2 compare на операцию у хипа.
По 1 сравнению на каждую проверяемую ноду, как и в линейном случае.
Линейный случай может выиграть только за счет более раннего выхода, ибо у него скважность 1, а не 2.
Еще у него более регулярный доступ в пределах варпа, нету разброса по индексам, может зарешать, если у современных GPU проблемы со scatter/gather-доступом к регистровому файлу.

#52
4:39, 12 июля 2019

}:+()___ [Smile]
> По 1 сравнению на каждую проверяемую ноду, как и в линейном случае.
Я вот смотрю на код:

void ShiftDown(int* heads, int idx) {
    int el=heads[idx];
    while(true) {
        int idx2=2*idx+1;
        if(idx2>=N) break;
        idx2+=(idx2+1<N && GetPointsData(heads[idx2+1])<GetPointsData(heads[idx2]));
        if(GetPointsData(heads[idx])<=GetPointsData(heads[idx2])) break;
        heads[idx]=heads[idx2];
        idx=idx2;
    }
    heads[idx]=el;
}
и вижу 2 сравнения. Сначала сравниваем узлы поддерева, и выбираем минимальный. Потом сравниваем минимальный узел с текущим значением.
Я понимаю, что если мы сравнили idx2 и (idx2+1), а затем выбрали idx2, то idx с (idx2+1) уже не будут сравниваться. Но мы то уже сделали 2 сравнения, в то время как для линейного случая мы можем сделать одно сравнение. По количеству сравнений хип догоняет линейный только на 4-ом элементе. Плюс у хипа есть дополнительная операция: 2*idx+1.
В общем без тестов от суслика тут не обойтись.
#53
4:44, 12 июля 2019

На всякий случай проапдейчу свой линейный алгоритм с оптимизациями, подсказанными Aslan-ом

float GetPointsData(int idx) {
  if (idx == -1) return MAX_VALUE;
  return points[idx].data;
}

int heads[N];
SortHeads(heads); //сортируем головы по data полю

while (heads[0] != -1) {
  process(points[heads[0]].data); //обрабатываем минимальную data
  heads[0] = points[heads[0]].next; //апдейтим голову

  int el = heads[0];
  int i = 0;
  while (i < N-1) { //поддерживаем инвариант по минимальной data
    if (GetPointsData(el) > GetPointsData(heads[i+1])) {
      heads[i] = heads[i+1];
    } else {
      break; //выходим из цикла раньше, если можно
    }
    i++;
  }
  heads[i+1] = el;
}

#54
(Правка: 12:42) 12:41, 12 июля 2019

totoro
> Некоторые считают, что не ставить закрывашку в однострочных бранчах вредно.
Я не про это, ты не понял.
Я тоже за

if (cond) 
{
  block
  block
  block
}
Так проще парные скобки искать.

Но есть else, то нет никакого смысла уделять ему личную строчку:

if (cond) 
{
  block
  block
  block
} else
{
  block
  block
  block
}

totoro
> Были бы скобки - сэкономилась бы пара часов при отладке
Это уже не вопрос переноса, а вопрос обязательности операторных скобок.

#55
(Правка: 15:07) 15:03, 12 июля 2019

MrShoor
Еще можно попробовать закэшировать heads[idx], heads[idx2] в стэковых переменных, разыменование указателя - это два чтения, +чтение индекса, тогда как из стэковой/глобальной переменной чтение по compile-time адресу

#56
17:39, 12 июля 2019

Aslan
> Еще можно попробовать закэшировать heads[idx], heads[idx2] в стэковых
> переменных, разыменование указателя - это два чтения, +чтение индекса, тогда
> как из стэковой/глобальной переменной чтение по compile-time адресу
Если это будет на gpu, то оно итак там будет закешировано

#57
13:35, 28 июля 2019

Тупой вопрос, так как постов с кодом много = как хорошо код в нулевом топике подходит для сортировки объектов по глубине кадра?
Не буду пока заморачиваться на шейдерах, спрашиваю про код на C++.

#58
14:35, 28 июля 2019

Daniil Petrov
на cpu просто используй std::sort и не парься.

#59
14:58, 28 июля 2019

Suslik
> на cpu просто используй std::sort и не парься.
По скорости для каждого кадра нормально?

Страницы: 1 2 3 4 5 Следующая »
ПрограммированиеФорумОбщее