1. Си / Говнокод #19366

    −51

    1. 01
    2. 02
    3. 03
    4. 04
    5. 05
    6. 06
    7. 07
    8. 08
    9. 09
    10. 10
    11. 11
    12. 12
    13. 13
    14. 14
    15. 15
    16. 16
    17. 17
    18. 18
    19. 19
    20. 20
    21. 21
    22. 22
    23. 23
    24. 24
    25. 25
    26. 26
    27. 27
    28. 28
    29. 29
    30. 30
    31. 31
    32. 32
    33. 33
    34. 34
    35. 35
    36. 36
    37. 37
    38. 38
    39. 39
    40. 40
    41. 41
    42. 42
    43. 43
    44. 44
    45. 45
    46. 46
    47. 47
    48. 48
    49. 49
    50. 50
    51. 51
    52. 52
    53. 53
    54. 54
    #include <stdio.h>
     
    #define XORSWAP(a, b) ((a)^=(b),(b)^=(a),(a)^=(b))
     
    static int heap_size;
     
    int parent(int i){
    	return i >> 1;
    }
     
    int left(int i){
    	return i << 1;
    }
     
    int right(int i){
    	return (i << 1) | 0x1;
    }
     
    void heapify(int *h, int i){
    	int l = left(i);
    	int r = right(i);
    	int largest;
     
    	if(l <= heap_size && h[l] > h[i])
    		largest = l;
    	else
    		largest = i;
     
    	if(r <= heap_size && h[r] > h[largest])
    		largest = r;
     
    	if(largest != i){
    		XORSWAP(h[i], h[largest]);
    		heapify(h, largest);
    	}
    }
     
    void make_heap(int *h, int len){
    	int i;
    	heap_size = len;
     
    	for(i = len/2; i >= 1; i--)
    		heapify(h, i);
    }
     
    int main(int argc, char *argv[]){
    	int i;
    	int h[11] = {0, 1, 3, 5, 7, 9, 2, 4, 6, 8, 10};
     
    	make_heap(h, 11);
    	for(i = 1; i < 11; i++)
            printf((i + 1 == 11) ? "%d" : "%d ", h[i]);
    	return 0;
    }

    Сказали, что качество говнокода лучше обсудить здесь.

    Запостил: HiewMorjowie, 28 Января 2016

    Комментарии (32) RSS

    • > heapify
      Ответить
      • Окучивание.
        Ответить
      • Функция так в литературе и называется.

        Только вроде она должна быть с линейной сложностью, а тут что-то непонятное.
        Ответить
        • Не линейной, а логарифм наверное.
          Ответить
          • http://stackoverflow.com/questions/9755721

            Но похоже что у ОПа все нормально. Т.е. это только кажется что сложность выше.
            Ответить
    • Ну что ж, начнём ревью...

      > XORSWAP
      Нинужно. Делай нормальный свап в виде функции и не выябывайся знанием макросов и битовой магии.

      > heap_size
      Почему у тебя размер массива в глобалке? Передай его параметром.

      > l <= heap_size
      > for(i = 1; i < 11; i++)
      Это залёт... за границу массива. В си массивы с нуля. Ну и все parent/child и .тп. у тебя тоже написаны для массивов с единицы.

      > for(i = len/2; i >= 1; i--)
      Деление пополам там точно нужно? Я не уверен, но вроде надо было все ноды окучивать.

      P.S. Лабы на ГК не постят.
      Ответить
      • Это не первая лаба опа
        Ответить
      • >В си массивы с нуля
        И тогда не получится сделать хиккерскую магию здесь: return (i << 1) | 0x1;
        У Кормена индексы тоже с единицы для общности, а у Левитина они с единицы сознательно, хотя все его псевдокоды заточены под си. Нулевой элемент не используется.
        И да, это не лаба. Посоветуйте, где можно посмотреть профессиональную реализацию структур в реальных проектах. Гуглится одно только лабное говно с убогим, негибким интерфейсом.
        Ответить
        • > Нулевой элемент не используется.
          Ну окей, окей, уговорил. Только один хер за границу вылетаешь. Нету в этом массиве 11-го элемента.
          Ответить
          • Очень хуевый интерфейс получается. Неуниверсально и жестко. Переменную heap_size надо либо делать глобальной и прятать в .c-сорце, либо передавать как параметр, а значит, что место использования кучи обрастает раком.
            Ответить
            • > надо либо делать глобальной
              И навсегда забыть о тредах (можно в тредлокал засунуть, но это тот ещё костыль).

              > либо передавать как параметр
              Либо положить и указатель и длину в структуру и таскать их всегда вместе.
              Ответить
              • > Либо положить и указатель и длину в структуру и таскать их всегда вместе.
                Ты ему так очень тонко предлагаешь уйти в С++ же?
                Ответить
          • Можно просто объявить указатель, который на 1 меньше чем нулевой элемент массива, и тогда нулевой элемент этого указателя будет первым
            Ответить
            • А в нулевой элемент положить длину. Тогда и глобалка не понадобится.
              Ответить
        • > негибким интерфейсом
          Ну не сделаешь ты на чистой сишке гибкий интерфейс. Смирись. Не знаю, что именно ты хочешь гибкого. Но если функцию, работающую с произвольными типами - то в итоге всё выльется в void* обёрнутый в какое-нибудь макроговно, или в memcpy или во вложенную структуру и container_of.
          Ответить
        • > И да, это не лаба.
          А что это? :) Ну ок, проект для самообучения основам алгоритмов и проектирования. По сути та же лаба, только сдаёшь себе вместо препода.
          Ответить
          • >А что это? :)
            Везде говорят, что иногда требуется писать структуры данных с нуля типа расширений красно-черных деревьев для нахождения порядковых статистик. На деле написать их не так сложно, как сделать их пригодными для использования.
            Ответить
            • Стандартный подход:
              - состояние твоего контейнера загоняешь в структуру
              - указатель на структуру передаешь во все "методы"
              - ...
              - профит
              Ответить
        • > Посоветуйте, где можно посмотреть профессиональную реализацию структур в реальных проектах.
          > Куча
          > Профессиональная структура данных
          /0
          Обычно от неё толку, что с козла - молока. Оно вроде и есть, но никто его не пьет.
          Ответить
          • priority queue
            Ответить
            • Кстати всегда было интересно, почему куча в стд представлена алгоритмами, а не контейнерами?
              И почему среди алгоритмов кучи, нет реализации для кучи как структуры данных на основе дерева через линки поинтеров, должно быстрее вставляться в такую кучу
              Ответить
              • > почему куча в стд представлена алгоритмами
                Для прикладных целей есть std::priority_queue. Зачем тебе нужна голая куча как контейнер? А если heap sort на её основе мутить - контейнер вместо алгоритма вообще палки в колёса будет вставлять.

                > на основе дерева
                Да ну... Памяти жрёт больше, хуёво кешируется, дрочит аллокатор на каждый чих (последние 2 пункта вроде как пофиксятся кастомным аллокатором)... Ну и скатывание элемента один фиг будет править кучу линков по дороге. Так что если элементы мелкие - можно и в проигрыше остаться.
                Ответить
                • А зачем тебе править кучу линков по дороге? Сразу пробежался по нодам до нужного места и без свапа пихнул в нужное место
                  Ответить
                  • > пихнул
                    Проблемы начнутся при вытаскивании же, не при впихивании. У тебя в корне самый большой элемент, ты его выдираешь. Соотв. надо на его место скатить одного из потомков и т.п. Или я туплю?
                    Ответить
              • > И почему среди алгоритмов кучи, нет реализации для кучи как структуры данных на основе дерева через линки поинтеров, должно быстрее вставляться в такую кучу

                Use std::multiset, Luke.
                Ответить
        • По-моему никто не реализует свою-очередную-супер-быструю-структуру-данных-хотя-на-самом-деле-валится-через-раз, а использует готовые решения (библиотеки).
          Ответить
    • >#define XORSWAP

      Бля, вот я понимаю вашу(си\плюсовиков) любовь к макросам. Но почему тогда либо не все вынести в макросы, либо чуть более по-человечески в функции?
      Ответить

    Добавить комментарий