Здравствуйте, Mamut, Вы писали:
M> Ops>90% покрывает константность/константные ссылки. Остальное да, надо тратить время, продумывая поведение. Зато можно дешево if(s[0]=='a') s[0]='b';
M> Только вот даром эта дешевость никому не нужна. Потому что все давно живут в эпоху юникода и s[0] == 'ö' уже не прокатит.
Мамут забавный. Смотри, показываю один раз:
var s : UnicodeString; // WideStringbegin
s := '中文';
if s[1] = '中'then
s[1] := '文';
end;
В чем проблема-то? Строки с двухбайтовым символом, покрывают весь BMP. Строки с четырехбайтовым символом покрывают весь юникод вообще. Но достаточно и двухбайтового символа т.к. все что за BMP практически не используется.
Здравствуйте, Pavel Dvorkin, Вы писали:
PD>то для 10000 должно быть в 100 раз больше, то есть 500 секунд. Запусти, завтра скажешь, когда закончилась. А может, не завтра
Павел, будут ли комментарии к этому
Здравствуйте, Pavel Dvorkin, Вы писали:
PD> Возможно, ты и прав, но все эти отличия примерно те же, что и для ранней версии С++ (BC++ 2.0) vs версии времен BC++5.0.
Мой интерес к сям пропал раньше, чем вышел BC++5.0
Здравствуйте, hattab, Вы писали:
M>> Только вот даром эта дешевость никому не нужна. Потому что все давно живут в эпоху юникода и s[0] == 'ö' уже не прокатит.
H>Мамут забавный. Смотри, показываю один раз:
Это ты забавный.
H>В чем проблема-то? Строки с двухбайтовым символом, покрывают весь BMP.
Ты лучше покажи, что будет, если ты попытаешься в строке "ёкарный трамвай" заменить s[0] таким методом. При том, что она набрана следующим образом:
и видимая тобой "ё" представляет сумму 0435 (е) и 0308 (две точки сверху).
Это я так тонко, не используя специальных терминов, намекнул на тему Normalization forms.
H>Строки с четырехбайтовым символом покрывают весь юникод вообще.
Нету в юникоде "двухбайтового символа" или "четырёхбайтового символа". Символ может быть хоть 20-байтовым, потому что состоит из базового кодового пункта и модификаторов.
А ты продолжаешь считать, что символ == кодовый пункт. Ну что ж, до первого столба.
The God is real, unless declared integer.
Re[8]: ответ на вопрос: Почему новые программы работают меделнно
Здравствуйте, netch80, Вы писали:
n> Ты лучше покажи, что будет, если ты попытаешься в строке "ёкарный трамвай" заменить s[0] таким методом. При том, что она набрана следующим образом:
n> $ echo 'ёкарный трамвай' | iconv -t utf-16be | hd n> 00000000 04 35 03 08 04 3a 04 30 04 40 04 3d 04 4b 04 39 |.5...:.0.@.=.K.9| n> 00000010 00 20 04 42 04 40 04 30 04 3c 04 32 04 30 04 39 |. .B.@.0.<.2.0.9| n> 00000020 00 0a |..| n> 00000022
n> и видимая тобой "ё" представляет сумму 0435 (е) и 0308 (две точки сверху).
Здравствуйте, hattab, Вы писали:
H>NormalizeString, а дальше, как обычно.
Переупрощаешь. Нормализация может дать и несколько символов.
Именно посимвольные сравнения начинают терять смысл, остаются только поиски подстрок. А это дороже.
The God is real, unless declared integer.
Re[21]: ответ на вопрос: Почему новые программы работают меделнно
Здравствуйте, Pavel Dvorkin, Вы писали:
PD>Именно. Зная структуру данных и алгоритм, сделаю вывод. Увижу массив и линейный цикл — сделаю вывод, что O(N).
Не угадал. Дальше что?
Увидел не массив, а некую структуру CCustomList. Увидел не цикл, а некий вызов типа std::sort(). Какой будет O()?
Уйдемте отсюда, Румата! У вас слишком богатые погреба.
Re[10]: ответ на вопрос: Почему новые программы работают меделнно
Здравствуйте, netch80, Вы писали:
n> H>NormalizeString, а дальше, как обычно.
n> Переупрощаешь. Нормализация может дать и несколько символов. n> Именно посимвольные сравнения начинают терять смысл, остаются только поиски подстрок. А это дороже.
А тут речь не о поиске, а о модификации строки. Тут, вообще говоря, пофиг на нормализации и формы представления т.к. обсуждается мутабельность vs. иммутабельность. А с мутабельными строками можно ведь и группу символов заменить:
s:='1234567890';
Delete(s, 5, 3); // удаление трех символов с пятой позиции
Insert('4321', s, 5); // вставка подстроки в пятую позицию
Здравствуйте, MxMsk, Вы писали:
MM>Здравствуйте, Pavel Dvorkin, Вы писали:
PD>>то для 10000 должно быть в 100 раз больше, то есть 500 секунд. Запусти, завтра скажешь, когда закончилась. А может, не завтра MM>Павел, будут ли комментарии к этому
Что-то долго от тебя ответа не было. Я уж думал, что ты и впрямь запустил тот код при N == 10000, и он все еще работает
На то решение комментарий дам, здесь.
Я его пробовал. Работает вполне успешно. Я не сравнивал его по скорости с императивным.
Так что можно подвести итоги.
1. Я не отрицаю, что на LinQ можно написать код более или менее приемлемый. Глупо было бы это отрицать — если бы это было так, LinQ давно бы помер.
2. В то же время я вынужден констатировать, что на LinQ можно написать код, скорость работы которого категорически неприемлема.
3. Никаких критериев, позволяющих сказать, в каком случае скорость будет приемлемой, а в каком нет, я так и не услышал. Кроме совета использовать голову. Использовать голову, конечно, надо, только для императивного кода к этому прилагается еще обширная информация о временнОй сложности тех или иных алгоритмов.
4. Попытка определить временнУю сложность этого несчастного кода, сделанная тобой и Mamut (ты привел численные данные, а он попробовал дать некоторое обоснование) вполне провалилась.
Вот и все.
With best regards
Pavel Dvorkin
Re[29]: ответ на вопрос: Почему новые программы работают меделнно
PD>1. Я не отрицаю, что на LinQ можно написать код более или менее приемлемый. Глупо было бы это отрицать — если бы это было так, LinQ давно бы помер. PD>2. В то же время я вынужден констатировать, что на LinQ можно написать код, скорость работы которого категорически неприемлема.
Аналогично для С++, примеры кода тут были
PD>3. Никаких критериев, позволяющих сказать, в каком случае скорость будет приемлемой, а в каком нет, я так и не услышал. Кроме совета использовать голову. Использовать голову, конечно, надо, только для императивного кода к этому прилагается еще обширная информация о временнОй сложности тех или иных алгоритмов. PD>4. Попытка определить временнУю сложность этого несчастного кода, сделанная тобой и Mamut (ты привел численные данные, а он попробовал дать некоторое обоснование) вполне провалилась.
Что-то мы давно с тобой не схватывались
PD>>Именно. Зная структуру данных и алгоритм, сделаю вывод. Увижу массив и линейный цикл — сделаю вывод, что O(N). S>Не угадал. Дальше что?
Я вообще-то гаданиями не занимаюсь. Если ты хотел сказать, что бывают циклы, при которых массив проходится не весь — ты безусловно прав, но это тривиальность. Естественно, надо смотреть, как именно выглядит цикл и что там делается. Я же имел в виду линейный проход по всему линейному массиву, как нетрудно догадаться.
S>Увидел не массив, а некую структуру CCustomList. Увидел не цикл, а некий вызов типа std::sort(). Какой будет O()?
Антон, ну не стоит так уж. Если уж о sort речь пошла, то в его quicksort имплементации вообще не цикл, а рекурсия (можно и без нее, конечно), но это не помешало еще N лет назад оценить форму зависмости t= f(N) . Аналитически определить, заметь. Что касается std::sort, то вопрос о ее временной зависимости можешь задать в форуме C++, там тебе сильно удивятся и посоветуют пройти заново основы.
Или можешь обратиться в форум "Алгоритмы", там для каждого второго топика обсуждается временнАя зависимость алгоритма от N. Там тебе все, что нужно, объяснят, а меня уволь.
With best regards
Pavel Dvorkin
Re[29]: ответ на вопрос: Почему новые программы работают меделнно
Здравствуйте, Pavel Dvorkin, Вы писали:
PD>4. Попытка определить временнУю сложность этого несчастного кода, сделанная тобой и Mamut (ты привел численные данные, а он попробовал дать некоторое обоснование) вполне провалилась.
Я сразу утверждал, что код плох и объяснил, почему вменяемый разработчик не стал бы такое делать. На мой взгляд, одно это уже говорит, что оценка изначально плохого кода — дело неблагодарное. Но мы решили потратить время, ок. Да, я упустил из виду Concat, и что? Я не могу ошибаться? Ну, хорошо, я не имел право на ошибку (хотя, учитывая первое предложение, я бы не дал ей даже повода). Однако, Павел, ты разве требовал дать оценку? Не фига подобного. Изнальный вопрос был, какие правила. Теперь ты видишь, какие правила. Такие же, как и у императивного кода. Невнимание к Concat — это моя "студенческая" ошибка, не имеющая никакого отношения к теории.
Re[30]: ответ на вопрос: Почему новые программы работают меделнно
Здравствуйте, Mamut, Вы писали:
PD>>4. Попытка определить временнУю сложность этого несчастного кода, сделанная тобой и Mamut (ты привел численные данные, а он попробовал дать некоторое обоснование) вполне провалилась. M>Это звиздец. http://rsdn.ru/forum/flame.comp/4796524.1.aspx
Ну да. Постфактум уже что-то объяснили — после того, как я нашёл, что именно надо объяснить.
M>Я же говорю, ты видишь ровно только то, что хочешь видеть.
Интересно, зачем ты откровенно врёшь тогда, когда тривиально можно поднять всю ветку и увидеть связи и последовательность?
Думаешь, что никто не захочет мараться об твою ложь?
The God is real, unless declared integer.
Re[23]: ответ на вопрос: Почему новые программы работают меделнно
Здравствуйте, Pavel Dvorkin, Вы писали:
PD>Я вообще-то гаданиями не занимаюсь.
Да ладно. PD>Если ты хотел сказать, что бывают циклы, при которых массив проходится не весь — ты безусловно прав, но это тривиальность.
Я, естественно, хотел сказать, что за предположение о константности времени выполнения операции a[i] без проверки того, как реализован operator[] для этого a, нужно сразу же отправлять в астрологический колледж.
S>>Увидел не массив, а некую структуру CCustomList. Увидел не цикл, а некий вызов типа std::sort(). Какой будет O()?
PD>Антон, ну не стоит так уж. Если уж о sort речь пошла, то в его quicksort имплементации вообще не цикл,
Бонус за внимательность уходит в зал. PD>а рекурсия (можно и без нее, конечно), но это не помешало еще N лет назад оценить форму зависмости t= f(N) . Аналитически определить, заметь. Что касается std::sort, то вопрос о ее временной зависимости можешь задать в форуме C++, там тебе сильно удивятся и посоветуют пройти заново основы.
О, воинствующая некомпетентность на марше. На всякий случай напомню, что стандарт C++ описывает не "временную зависимость", а количество сравнений. Которое, кстати, может в плохих случаях достигать N^2.
А временная зависимость будет очень шибко зависеть от реализации компаратора и оператора [] классе скормленных в std::sort итераторов.
В частности, связный список будет сортироваться std::sort-ом вовсе не за O(NlogN). А не заглядывая в реализацию ССustomList ты никаких предположений о его внутреннем устройстве сделать не сможешь. Это тебе не C, где a[i] всегда равно i[a].
Уйдемте отсюда, Румата! У вас слишком богатые погреба.
Re[31]: ответ на вопрос: Почему новые программы работают меделнно
Здравствуйте, netch80, Вы писали:
N>Ну да. Постфактум уже что-то объяснили — после того, как я нашёл, что именно надо объяснить.
Лично у меня, как и у многих других, просто не было желания тратить время на дальнейшее разбирательство в коде. Знаешь почему? Потому что было очевидно, что Павлу этого не надо. Вот когда ты включился, тогда появилась заинтересованность.
Re[29]: ответ на вопрос: Почему новые программы работают меделнно
PD>3. Никаких критериев, позволяющих сказать, в каком случае скорость будет приемлемой, а в каком нет, я так и не услышал. Кроме совета использовать голову. Использовать голову, конечно, надо, только для императивного кода к этому прилагается еще обширная информация о временнОй сложности тех или иных алгоритмов. PD>4. Попытка определить временнУю сложность этого несчастного кода, сделанная тобой и Mamut (ты привел численные данные, а он попробовал дать некоторое обоснование) вполне провалилась.
Ну и вдогонку, раз ты такой умный, а мы все такие тупые. Расскажи про сложность чего-нить типа
int v[] = { 1, 4, 5 };
std::shared_ptr<IEnumerable<int>> source(new Vector<int>(v, ARRAYSIZE(v)));
source->Aggregate(
[](IEnumerable<int> *current, int value){
if(current -> Count() == 0){
int v1[] = {0};
std::shared_ptr<IEnumerable<int>> source(new Vector<int>(v1, ARRAYSIZE(v1)));
return source;
} else {
int v1[] = {value + current -> Last()};
std::shared_ptr<IEnumerable<int>> source(new Vector<int>(v1, ARRAYSIZE(v1)));
return current -> Concat(source);
}
}
);
Чистейший C++. Взято на основе тут. Код не обязательно 100% корректный, он здесь для определения уровня понимания.
PD>>>4. Попытка определить временнУю сложность этого несчастного кода, сделанная тобой и Mamut (ты привел численные данные, а он попробовал дать некоторое обоснование) вполне провалилась. M>>Это звиздец. http://rsdn.ru/forum/flame.comp/4796524.1.aspx
M>>Провалилась попытка у него. Нуну.
N>Ну да. Постфактум уже что-то объяснили — после того, как я нашёл, что именно надо объяснить.
Что и где ты нашел?
M>>Я же говорю, ты видишь ровно только то, что хочешь видеть.
N>Интересно, зачем ты откровенно врёшь тогда, когда тривиально можно поднять всю ветку и увидеть связи и последовательность? N>Думаешь, что никто не захочет мараться об твою ложь?
У меня нет ни малейшего желания занииматься разбором твоей софистики. Ты прекрасно понимал, что речь там шла отнюдь не о случаях доступа через operator[],а о прямой индексации в стиле С, в противном случае мы имеем вызов функции operator[] внутри цикла, а это надо учитывать, если ее реализация не O(1). Равно как и все остальное. Суть выводов это никак не меняет.
With best regards
Pavel Dvorkin
Re[30]: ответ на вопрос: Почему новые программы работают меделнно
Здравствуйте, MxMsk, Вы писали:
PD>>4. Попытка определить временнУю сложность этого несчастного кода, сделанная тобой и Mamut (ты привел численные данные, а он попробовал дать некоторое обоснование) вполне провалилась. MM>Я сразу утверждал, что код плох и объяснил, почему вменяемый разработчик не стал бы такое делать. На мой взгляд, одно это уже говорит, что оценка изначально плохого кода — дело неблагодарное. Но мы решили потратить время, ок. Да, я упустил из виду Concat, и что? Я не могу ошибаться? Ну, хорошо, я не имел право на ошибку (хотя, учитывая первое предложение, я бы не дал ей даже повода). Однако, Павел, ты разве требовал дать оценку? Не фига подобного. Изнальный вопрос был, какие правила. Теперь ты видишь, какие правила. Такие же, как и у императивного кода. Невнимание к Concat — это моя "студенческая" ошибка, не имеющая никакого отношения к теории.
Ну что же, все верно. Ошибку в укор тебе ставить не буду, конечно. Правда, тот факт, что ее никто не заметил , пока не было произведено сравнение с экспериментом, тоже кое о чем говорит...
В общем, могу согласиться, что какие-то правила, наверное, существуют. Плохо лишь то, что их толком сформулировать — получается плохо. Отсюда большой риск получить весьма (пусть не настолько, как в этом примере) неэффективный код. Если эти правила будут где-то внятно изложены, если любой учебник по LinQ будет их содержать, тогда, наверное, можно будет как-то иначе к этому относиться.
