Stack Overflow на русском - 2017-03-27 (page 3 of 3)

« first day (726 days earlier) ← previous day next day → last day (2587 days later) »

8:00 PM

Сейчас весь ДжаваСкрипт тяжело вздохнул... Он же не зря называется функциональным языком! Юзай функции. Это их первое призвание вообще, избавлять код от повторений. — VostokSisters 47 secs ago

Алексей Шиманский

@vp_arth призвание функций избавлять код от повторений? ммм...

@АлексейШиманский Вроде не Vadizar) Но порой вызывает похожие чувства)

Алексей Шиманский

@vp_arth да школолошник с ЧСВ, ничего новго

Nicolas Chabanovsky

@Other Как мне кажется, подойдет вопрос на Мете. Что скажите?

@NicolasChabanovsky @Other я за. Го на мету) Чатик, если понадобится к мете прикрутим.

8:15 PM

@VladD, @D-side, похоже у нашего знакомого с софтами новый ник

ru.stackoverflow.com/q/644958/186999

Алексей Шиманский

> Есть массив с форичами

@Grundy удалённые вопросы не раскрываются) это нечестно)

Алексей Шиманский

@vp_arth Делай как маленький Grundy: собирай коллекцию, как стукнет 10к - читай.

8:31 PM

> Вы заработали знак «Pundit» (Leave 10 comments with score of 5 or more).

Тут ещё и за комменты бейджи выдают)

Алексей Шиманский

9:01 PM

я конечно благодарен, но я вообще не понимаю нахрена вы превращаете замечательный язык программирования в нечитаемую кашу в которой хрен разберёшься, это убого, ломает мозг, глаза и всё удовольствие от программирования. но зато можно выпендриваться, не спорю. — Khipster 6 mins ago

@Other ^^^

вот вот вот. о чем я и говорил

для новичков частенько непонятны такие творения.

@АлексейШиманский ++_ и не новичкам глаза жжёт..

Алексей Шиманский

@vp_arth это мутант с двумя глазами на одной стороне)

Надо быть проще. Скопировал код с enSO и гуляй смело :D

// вспомнил самый нормально выглядящий шафл:
[1, 2, 3, 4, 5].sort(function() {
  return 0.5 - Math.random();
});

@АлексейШиманский ну вот, сохранился коммент для истории. Он его изменил

9:19 PM

@vp_arth нет, он ненормально выглядит. 1 - оно работает за n log n а не за n. 2 - почему оно вообще работает? Напишите такое в С++ получите выход за границу массива из-за нарушения контракта на оператор сравнения.

@pavel 1. вы размер массива видите? 2. Что не так с контрактом? В Array.sort - важен только знак.

@Other Я думаю, найдутся достойные ~~поедатели морковки~~ программисты

@VladD куда в отпуск-то хоть? или дома?

@vp_arth По контракту сравнение должно гарантировано (а) возвращать одинаковый результат для одних и тех же значений, (б) быть антисимметричным, иррефлексивным и транзитивным

@vp_arth На море!

Греть уши на солнышке

@VladD какой такой алгоритм сортировки дважды сравнивает одну и ту же пару элементов?

9:26 PM

@vp_arth Имеет право

Хуже того, если он сравнивает не каждую пару, то неплохо бы, чтобы из a < b и b < c следовало, что a < c

user image

@vp_arth Это ж моё селфи!

@vp_arth похоже, рассвет на Бали (около 6 утра)

@vp_arth Хм, неужели квиксорт ни разу не сравнивает одну и ту же пару?

@VladD а зачем? какой он после этого квиксорт?

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

9:31 PM

@vp_arth Ну так сходу не очевидно

Там же вроде не пары элементов вообще сравниваются, а элементы с пивотом, который в общем случае не обязан быть в массиве.

@vp_arth Ну это да, но обычно ж выбирают один из элементов массива?

@VladD для чисел часто выбирают avg(min, max)

@vp_arth Хм, а откуда известен min?

@VladD это всего лишь O(n), можно пробежаться разок)

9:37 PM

@vp_arth ну это только первый пивот

а нужно ж на каждой итерации

@VladD а там avg(min, pivot) или avg(pivot, max)

@vp_arth мы куда-то сошли с темы :) это всё равно по идее не доказывает, что одна и та же пара не будет сравниваться дважды

даже если такой алгоритм и применяется

тем более, если сравнение «плавает», то элемент, который при сравнении оказался меньше, чем пивот, может при следующем сравнении оказаться больше, так что массив выйдет неотсортированным

@VladD сравнении с чем?

что уж совсем никуда не годится

@vp_arth с пивотом

@VladD так скалярное сравнение никуда не плавает. Да и задача у нас получить равномерно перемешанный массив, а не отсортированный)

9:42 PM

ну, мы сравниваем с пивотом, и допустим, что элемент получился меньше. мы отсюда делаем вывод, что его можно поместить в «левую» группу, и он будет меньше всех элементов правой группы

1

Q: std::sort ( from <algorithm> ) crashes

The following program, a simple vector sorting one, crashes for t >= 17 at the second sort invocation. First sort succeeds even for t == 100. Struggled for quite some time but I'm not able to figure out what is wrong. Can someone please help me? I've tried it on a MacBook Air as well as a linux ...

c++ linux stl stl-algorithm

Ну и всё, а на следующей итерации он с равной долей вероятности попадёт слева или справа от следующего пивота. Обратно за старый пивот ему дороги нет

11

A: C# List.Sort doesn't sort

To expand on 500 Internal Server Error's (correct) answer, Quicksort requires a well-behaved comparison function. You are required to provide a comparison that: is reflexive: an item must compare equal to itself is antisymmetric in inequality: if A is greater than B then B must also be smaller...

Это примеры к тому, что квиксорт имеет право крешнуться

как на C++, так и на C#

@VladD странные реализации просто) стандарт дал слишком много свободы, все дела

@vp_arth Ну, требование того, чтобы сравнивающая функция вела себя как сравнивающая функция, довольно естественно

Иначе непадающую сортировку тоже можно будет сделать, но (1) она будет менее эффективной, и (2) результат будет лишён смысла

потому что если a < b, b < c и c < a, каким должен быть правильный результат сортировки массива [a, b, c]?

так что требование естественно

а то, что мы хотим использовать алгоритм не по назначению, так это наши проблемы

ну и кроме того, эффективно перемешать массив можно без сортировки за O(n)

bool sort_cmp( int a, int b )
{
    return true;
}
vector<int> tv = {1, 2, 3, 4, 5};
int main()
{
    sort( tv.begin(), tv.begin()+5, sort_cmp); // ## This one works even for t == 100.
    for (int i : tv) {
        cout << i;
    }
    return 0;
}

54321

9:56 PM

@vp_arth Ну это как UB

Имеет право крешнуться. Имеет право не крешнуться.

и rand работает)

@vp_arth ну погоняйте с большим количеством элементов, крешнется

@VladD 1000 отлично зашаффлил

Тут дело только в реализации алгоритма - она имеет право быть кривой

по стандарту

Лям норм мешает, на 10 лямов cpp.sh не даёт памяти)

ideone.com/rD5Dg4

@VladD что за iota?

10:03 PM

@vp_arth Ну, мне не кажется, что реализация сортировки в gcc кривая. Если использовать не по назначению, имеет право не работать. Оттого, что микроскоп плохо забивает гвозди, он не становится плохим.

@vp_arth ну, она делает tv[i] = i + 1

чтобы не заполнять вручную

помните анекдот про чукотских рабочих и японскую бензопилу?

@VladD Про лом?

@vp_arth В моём варианте была рельса :)

Нормальные пацанские алгоритмы работают: ideone.com/7WJEL2

@VladD я только не понимаю, почему вы обсуждаете quicksort, да еще так, будто он делит на части до конца?

@avp а почему он не может делить их до конца?

10:09 PM

@avp Не, мы обсуждаем, можно ли алгоритму сортировки дать компаратор, который вычисляет результат по рандому

@vp_arth потому что это неэффективно. Последние несколько десятков сортируют вставками (или бинарными вставками)

@VladD не знаю, как на бинарных вставках он себя поведет. Не зациклится?

@avp эта оптимизация не является частью алгоритма

@vp_arth это практика. Лет 5 назад в ubuntu С++ sort был timsort-ом с бинарными вставками. Сейчас не знаю

@vp_arth ну, квиксорт как алгоритм тоже бывает с вариациями, например, тот же выбор пивота. в любом случае, предпочитают быстрый алгоритм, а для шаффла используют std::random_shuffle

@avp смысл использовать бинарные вставки для обычных int?

10:20 PM

@vp_arth спросите у тех, кто дистрибутив ваял

Ценность бинарных вставок по сравнению с обычными возрастает только в тех случаях, когда операция сравнения дольше сдвига массива после вставки

@vp_arth ну, учтите, что memove может быть весьма эффективен с векторными регистрами

@VladD это понятно, что nlogn в общем случае использовать дурость, даже если бы работало. Но в javascript на массиве из 5ти элементов считаю это нормальным

@avp ладно, приятно было поболтать, ребята) Я тут 5:22 на часах увидел... Ну нафиг, нет меня)

@vp_arth спокойной ночи! (Новосибирск?)

@avp он самый. Спасибо

10:25 PM

Спокойной ночи!

пойду-ка и я тоже, пора

10:37 PM

@VladD счастливо!

« first day (726 days earlier) ← previous day next day → last day (2587 days later) »

Transcript for

Mar '1727

Stack Overflow на русском

Генерал Дис Куссий несёт возмездие во имя ru.stackoverflow.com

qквери-плюгины бинайс драма киски модераторский-произвол нытьё филанизий

join this room
about this room

00:00

06:00

12:00

18:00

all times are UTC

site design / logo © 2024 Stack Exchange Inc; legal

mobile