Pull to refresh
41
0
Send message
По поводу использования O(n) памяти в QuickSort я таки докопался в чём там было дело.

Оказывается, в glibc есть 2 реализации быстрой сортировки — in-place вариант, который называется _quicksort, который можно найти в qsort.c, который я и рассматривал в оригинальной статье и не in-place вариант qsort_r, что в файле msort.c.

Так вот на самом деле по умолчанию используется именно qsort_r, т.е. вариант с O(n) по памяти. И только если памяти не хватает, в бой вступает in-place вариант:

0164 void
0165 qsort_r (void *b, size_t n, size_t s, __compar_d_fn_t cmp, void *arg)
0166 {
...
0175   if (size < 1024)
0176     /* The temporary array is small, so put it on the stack.  */
0177     p.t = __alloca (size);
0178   else
0179     {
...
0213       /* If the memory requirements are too high don't allocate memory.  */
0214       if (size / pagesize > (size_t) phys_pages)
0215     {
0216       _quicksort (b, n, s, cmp, arg);
0217       return;
0218     }
0219 
0220       /* It's somewhat large, so malloc it.  */
0221       int save = errno;
0222       tmp = malloc (size);
0223       __set_errno (save);
0224       if (tmp == NULL)
0225     {
0226       /* Couldn't get space, so use the slower algorithm
0227          that doesn't need a temporary array.  */
0228       _quicksort (b, n, s, cmp, arg);
0229       return;
0230     }
...
0254       msort_with_tmp (&p, p.t + n * sizeof (void *), n);


Забавно ещё то, что вызываемая функция msort_with_tmp — это Merge Sort, т.е. в абсолютном большинстве случаев, когда вы вызываете qsort в C, вы на самом деле делаете не QuickSort, а MergeSort.
У вас 64-битная машина?
Если вы об этой статье, то я, как автор, готов вам помочь. (Вообще не ожидал увидеть перевод своей статьи на хабр).
Круто, я пытался сделать что-то подобное, но не смог, поэтому заюзал lxc-контейнер. По cgroups очень сложно найти какую-то внятную документацию, чтобы человек извне мог понять что вообще происходит — к чему там все эти иерархии, контроллеры и пр. и как оно, собственно, работает. Может вы напишите кратенькую статейку-ликбез на эту тему?
Так а разве systemd-run не запустит программу под теми же cgroups? В чём тогда отличие от lxc в данном случае кроме управления через systemd и удобства?
Valgrind — это динамический отладчик для пользовательских приложений, про него информации уйма, в том числе на хабре. Про остальное я впервые слышу и не могу ничего нагуглить. Можно поподробнее, что такое NOP и SWAP?
Конечно, можно. Я скоро буду ковырять сам perf, думаю что-нибудь про него написать.
malloc принимает количество байт и возвращает нулевой указатель

malloc возвращает указатель на void. void — это не NULL
Не думаю, что мне подойдет ESXi, но спасибо за совет.
К сожалению, рабочие отношения с виндоус у меня не сложились, так что такой вариант отпадает.
Ага, понял, спасибо.
А спапшот виртуалки можно сделать? Чтобы я ловким движением руки, не запариваясь, восстановил как было. И сколько такое счастье будет весить?
Хочу на домашнем сервере развернуть гипервизор с несколькими виртуалками. Хочется что-то вроде одна виртуалка для разработки (LAMP, Postgres, git), другая с NAS, третья со всякой фигней типа mpd, vpn, торренты? Под NAS хочется полностью отдать 2 диска в md RAID1, другой диск отдать полностью под хранение разработки, и на четвертом нарезать LVM тома под ОСи для виртуалок.

1. Что удобнее с учетом вышеперечисленного?
2. Какие есть способы бэкапа виртуалок и сколько весят эти бэкапы?
Самое позорное, что это IEEE.
Зарплата на госпредприятиях уведет нас от вопросов экономики к вопросам гуманизма и человечности, поэтому эту категорию мы опустим.

В избранное.
Да, но зная тот масштаб и качество, с которым вы пишете статьи, отдельная статья по криптоанализу была бы просто бомбой!
Если у вас 1 КБ текста, то да — разницы нет. Но когда надо пошифровать гигабайты, то тут уж разница между 1 часом и 0.5 часа существенней будет.

Но вообще я не об этом — очень интересно было бы послушать о применении Haskell для решения задачи криптоанализа. Поэтому, когда вы начнете проходить более продвинутый курс в котором будет данная тема — вы знаете, что от вас будут ждать ;-)
Пятая и шестая — это Обмен ключами Шифрование при помощи открытых ключей?
А как же блочные и поточные шифры?
Крипта на функциональном языке — это, конечно, очень интересно. Но всё-таки мне кажется, что haskell бы больше подошел для решения задач криптоанализа, чем для реализации криптопримитивов.
Вы не пробовали замерять производительность вашего варианта на Haskell и C?
Ну почему же? В свое время, на первой встрече было сказано, что тематика группы не ограничена инфобезом, и данный доклад — тому подтверждение.

Information

Rating
Does not participate
Date of birth
Registered
Activity