Добро пожаловать в форум, Guest  >>   Войти | Регистрация | Поиск | Правила | В избранное | Подписаться
Все форумы / Программирование Новый топик    Ответить
Топик располагается на нескольких страницах: Ctrl  назад   1 2 3 4 5 6 [7] 8 9 10 11 .. 33   вперед  Ctrl
 Re: решение тривиальной алгоритмической задачи разными подходами и средствами  [new]
retty_jj_007
Member [заблокирован]

Откуда: Retville
Сообщений: 650
no-cl
retty_jj_007
Но вот что именно не учитываю...

Пример:
5
0 10
20 30
10 20
0 15
15 30
М = 2, К = 0, М-К = 2, ты даешь ответ - "2". А правильный ответ - "3".

Действительно... №2 просто вынужден чесать в ту же аудиторию
1 апр 09, 03:24    [7003020]     Ответить | Цитировать Сообщить модератору
 Re: решение тривиальной алгоритмической задачи разными подходами и средствами  [new]
Gluk (Kazan)
Member

Откуда:
Сообщений: 9372
студентик
содержит тип множество. Мне интересно как смогут программисты на С обойтись без него:)


Про битовые маски слышал ?
1 апр 09, 08:21    [7003152]     Ответить | Цитировать Сообщить модератору
 Re: решение тривиальной алгоритмической задачи разными подходами и средствами  [new]
студентик
Member

Откуда: Альфа Центавра
Сообщений: 294
Gluk (Kazan)
студентик
содержит тип множество. Мне интересно как смогут программисты на С обойтись без него:)


Про битовые маски слышал ?


слышал... но если не сложно хотя бы вкратце как использовать их в качестве множества через какие операторы?
1 апр 09, 10:50    [7003848]     Ответить | Цитировать Сообщить модератору
 Re: решение тривиальной алгоритмической задачи разными подходами и средствами  [new]
студентик
Member

Откуда: Альфа Центавра
Сообщений: 294
mayton
Gluk (Kazan)

Кинь по почте если не сложно :)
Я коллекционирую извращения

Отправил. Оба решения - не мои. Написали коллеги по работе. В варианте с SQL для пущей крутости можно использовать with с inline view. В варианте на Delphi используется custom-библиотека для вывода текста, но думаю это не помешает для понимания самого алгоритма.


погодите с решениями... задача в разработке)
1 апр 09, 10:56    [7003902]     Ответить | Цитировать Сообщить модератору
 Re: решение тривиальной алгоритмической задачи разными подходами и средствами  [new]
Gluk (Kazan)
Member

Откуда:
Сообщений: 9372
студентик
Gluk (Kazan)
студентик
содержит тип множество. Мне интересно как смогут программисты на С обойтись без него:)


Про битовые маски слышал ?


слышал... но если не сложно хотя бы вкратце как использовать их в качестве множества через какие операторы?


Каждый бит маски представляет элемент множества, что тут непонятного ?
1 апр 09, 11:46    [7004405]     Ответить | Цитировать Сообщить модератору
 Re: решение тривиальной алгоритмической задачи разными подходами и средствами  [new]
студентик
Member

Откуда: Альфа Центавра
Сообщений: 294
Gluk (Kazan)
студентик
Gluk (Kazan)
студентик
содержит тип множество. Мне интересно как смогут программисты на С обойтись без него:)


Про битовые маски слышал ?


слышал... но если не сложно хотя бы вкратце как использовать их в качестве множества через какие операторы?


Каждый бит маски представляет элемент множества, что тут непонятного ?


ну не знаю просто Паскаль к примеру реализует работу с множествами через эффективные машинные инструкции bts и bt, на С же без использования машинных команд реализовать множество через сдвиги или битовые операции будет не так эффективно и наглядно
1 апр 09, 11:55    [7004496]     Ответить | Цитировать Сообщить модератору
 Re: решение тривиальной алгоритмической задачи разными подходами и средствами  [new]
Gluk (Kazan)
Member

Откуда:
Сообщений: 9372
студентик
Gluk (Kazan)
студентик
Gluk (Kazan)
студентик
содержит тип множество. Мне интересно как смогут программисты на С обойтись без него:)


Про битовые маски слышал ?


слышал... но если не сложно хотя бы вкратце как использовать их в качестве множества через какие операторы?


Каждый бит маски представляет элемент множества, что тут непонятного ?


ну не знаю просто Паскаль к примеру реализует работу с множествами через эффективные машинные инструкции bts и bt, на С же без использования машинных команд реализовать множество через сдвиги или битовые операции будет не так эффективно и наглядно


Поверь мне, Си реализует битовые команды через не менее эффективные машинные инструкции.
Не веришь мне, поверь дизассемблеру
1 апр 09, 12:02    [7004571]     Ответить | Цитировать Сообщить модератору
 Re: решение тривиальной алгоритмической задачи разными подходами и средствами  [new]
no-cl
Guest
студентик
ну не знаю просто Паскаль к примеру реализует работу с множествами через эффективные машинные инструкции bts и bt, на С же без использования машинных команд реализовать множество через сдвиги или битовые операции будет не так эффективно и наглядно

А кто запрещает эти машинные команды-то использовать? Кстати, как там в паскале с ограничениями на размер множества? В турбо паскале было 256 элементов, сейчас так и осталось? Впрочем, поддержка на уровне языка весьма приятна, но вообще, на практике такие "множества" имеют крайне ограниченное применение, поскольку позволяют хранить только перечислимые подмножества. Как хранить, скажем, подмножество вещественных чисел? Множество вообще произвольных объектов, которые даже не упорядочиваются? Грошевое преимущество в скорости при почти полном отсутствии функциональности - смысл?
Ты довольно часто (как мне показалось) пишешь про оптимальность компиляции, крутоту низкоуровнего программирования, но вот проблема - на практике и то и другое дает мелочное ускорение, основные тормоза - из-за ошибок в архитектуре и в алгоритмах; первое так просто не обосновать, а вот второе - зарегься на spoj.pl, порешай сотню-другую задач, увидишь как всякие мега-быстрые с/с++/паскали могут под орех (то есть в тысячи и миллионы раз) разделываться всякими "неоптимальными" питонами-рубями просто использованием более правильных и эффективных алгоритмов.
1 апр 09, 12:15    [7004693]     Ответить | Цитировать Сообщить модератору
 Re: решение тривиальной алгоритмической задачи разными подходами и средствами  [new]
mayton
Member

Откуда: loopback
Сообщений: 38872
В С/C++ действительно нету ТИПА множество. Этот недостаток реализуется через внешние библиотеки функций (классов). Но что-бы сравнивать возможности "одних множеств" и "других" в Pascal и С надо задать начальные условия. Какое мы хотим множество? Будет ли оно расти? Как быстро? И насколько?
1 апр 09, 12:27    [7004817]     Ответить | Цитировать Сообщить модератору
 Re: решение тривиальной алгоритмической задачи разными подходами и средствами  [new]
vino
Member

Откуда:
Сообщений: 1191
no-cl
студентик
ну не знаю просто Паскаль к примеру реализует работу с множествами через эффективные машинные инструкции bts и bt, на С же без использования машинных команд реализовать множество через сдвиги или битовые операции будет не так эффективно и наглядно

А кто запрещает эти машинные команды-то использовать? Кстати, как там в паскале с ограничениями на размер множества? В турбо паскале было 256 элементов, сейчас так и осталось? Впрочем, поддержка на уровне языка весьма приятна, но вообще, на практике такие "множества" имеют крайне ограниченное применение, поскольку позволяют хранить только перечислимые подмножества. Как хранить, скажем, подмножество вещественных чисел? Множество вообще произвольных объектов, которые даже не упорядочиваются? Грошевое преимущество в скорости при почти полном отсутствии функциональности - смысл?

IMHO перед решением каждой задачи определяется прежде всего алгоритм, только потом - ЯП.
Ответы:
1) асм можно, но крайне не желательно использовать в решениях напрямую - для совместимости с разными платформами. Это к любому процедурному языку относится.
2) 256 элементов мало но эффективно, к тому же никто не мешает написать свою побитовую реализацию - и Pascal, и в C и в др.
3) подмножества любого типа и хранятся с использованием общих конструкций вроде дерева, но и расход памяти другой
4) битовые маски используются для экономии ОП, что важно при обработке огромных потоков данных, при чем тут "грошевое преимущество"? Да и в паскаль его ввели, когда ОП часто не исчислялась даже мегабайтами, чтобы упростить работу с сущностями типа множество. А сейчас, естественно, мало востребовано.
no-cl
Ты довольно часто (как мне показалось) пишешь про оптимальность компиляции, крутоту низкоуровнего программирования, но вот проблема - на практике и то и другое дает мелочное ускорение, основные тормоза - из-за ошибок в архитектуре и в алгоритмах; первое так просто не обосновать, а вот второе - зарегься на spoj.pl, порешай сотню-другую задач, увидишь как всякие мега-быстрые с/с++/паскали могут под орех (то есть в тысячи и миллионы раз) разделываться всякими "неоптимальными" питонами-рубями просто использованием более правильных и эффективных алгоритмов.

Не судите по себе! Возможно, в Вашей работе не требуется пресловутое "мелочное ускорение", так и не надо об этом говорить. А ошибки в архитектуре сейчас, в основном, из-за элементарной безграмотности, а учить теорию лень. Уверен, что низкоуровневый программист чаще уделяет внимание архитектуре и алгоритмам, чем высокоуровневый.
По поводу написанных (часто на коленке) супер-решениях - смотри IMHO.
1 апр 09, 12:51    [7005030]     Ответить | Цитировать Сообщить модератору
 Re: решение тривиальной алгоритмической задачи разными подходами и средствами  [new]
Gluk (Kazan)
Member

Откуда:
Сообщений: 9372
vino

Не судите по себе! Возможно, в Вашей работе не требуется пресловутое "мелочное ускорение"


А в Вашей требуется ?
Можно пару отвлеченных примеров из жизни ???
1 апр 09, 13:00    [7005115]     Ответить | Цитировать Сообщить модератору
 Re: решение тривиальной алгоритмической задачи разными подходами и средствами  [new]
vino
Member

Откуда:
Сообщений: 1191
Gluk (Kazan), например, сжатие и эффективная передача данных, программирование приборов с ограниченным объемом памяти или быстродействием. На самом деле очень много задач с ограниченным ресурсом по памяти или по быстродействию. В отличие от сверхдешевых PC, каналы связи и надежные ЭВМ не могут похвастаться излишками ресурсов.
1 апр 09, 13:07    [7005176]     Ответить | Цитировать Сообщить модератору
 Re: решение тривиальной алгоритмической задачи разными подходами и средствами  [new]
AlexandrPlus
Member

Откуда:
Сообщений: 7887
retty_jj_007
что-то вы темните...
В питоне это делается так (или уже было?)
Причем без физического перемещения элементов "массива"

>>> k = 3
>>> a = [1, 2, 3, 4, 5, 6, 7, 8, 9]
>>> a[:k], a[k:] = a[-k:], a[:len(a) - k]
>>> a
[7, 8, 9, 1, 2, 3, 4, 5, 6]
>>> 


до кучи
на питончике - одно выражение вообще

>>> k = 3
>>> a = (1,2,3,4,5,6,7)
>>> a = a[k:] + a[:k]
>>> a
(4, 5, 6, 7, 1, 2, 3)

>>> k = 3
>>> a = [1,2,3,4,5,6,7]
>>> a = a[k:] + a[:k]
>>> a
[4, 5, 6, 7, 1, 2, 3]
По краткости и ясности - питончик на первом месте.
1 апр 09, 13:21    [7005323]     Ответить | Цитировать Сообщить модератору
 Re: решение тривиальной алгоритмической задачи разными подходами и средствами  [new]
Q
Guest
А как же пролог??? :)
1 апр 09, 13:24    [7005353]     Ответить | Цитировать Сообщить модератору
 Re: решение тривиальной алгоритмической задачи разными подходами и средствами  [new]
AlexandrPlus
Member

Откуда:
Сообщений: 7887
Q
А как же пролог??? :)

в том виде еще надо append определять - две строчки

append([], L, L). 
append([X|L1], L2, [X|L3]):- append(L1, L2, L3).

без append - тоже больше одного клоза по любому
1 апр 09, 13:37    [7005511]     Ответить | Цитировать Сообщить модератору
 Re: решение тривиальной алгоритмической задачи разными подходами и средствами  [new]
vino
Member

Откуда:
Сообщений: 1191
AlexandrPlus, эффективность процесса программирования, в том числе лаконичность и межплатформенность Python, - подтверждаю
Только вот, к сожалению, заданные условия решения нарушены на все 100%
1 апр 09, 14:05    [7005796]     Ответить | Цитировать Сообщить модератору
 Re: решение тривиальной алгоритмической задачи разными подходами и средствами  [new]
студентик
Member

Откуда: Альфа Центавра
Сообщений: 294
ни в коем случае не хотел умалять возможности С и тем более значимость алгоритмов в программировании... нескрою, низкоуровневый код интересен мне, но я не переоцениваю его роль в сравнению с ВУЯП, более того имхо писать алгоритмы гораздо проще на ВУЯП, а затем переделывать его на том же самом ассемблере под конкретную реализацию. Просто был интересен вопрос по реализации множества в С...
1 апр 09, 14:11    [7005846]     Ответить | Цитировать Сообщить модератору
 Re: решение тривиальной алгоритмической задачи разными подходами и средствами  [new]
Gluk (Kazan)
Member

Откуда:
Сообщений: 9372
vino
Gluk (Kazan), например, сжатие и эффективная передача данных, программирование приборов с ограниченным объемом памяти или быстродействием. На самом деле очень много задач с ограниченным ресурсом по памяти или по быстродействию. В отличие от сверхдешевых PC, каналы связи и надежные ЭВМ не могут похвастаться излишками ресурсов.


Вы этим занимаетесь ?
1 апр 09, 14:15    [7005889]     Ответить | Цитировать Сообщить модератору
 Re: решение тривиальной алгоритмической задачи разными подходами и средствами  [new]
vino
Member

Откуда:
Сообщений: 1191
Gluk (Kazan)
Вы этим занимаетесь ?

хотя, вообще-то, перечислены классы задач - но по каждому из них имею реальный опыт
что-то конкретное интересует?
1 апр 09, 14:23    [7005950]     Ответить | Цитировать Сообщить модератору
 Re: решение тривиальной алгоритмической задачи разными подходами и средствами  [new]
студентик
Member

Откуда: Альфа Центавра
Сообщений: 294
прошу не судить меня строго за написанное:) тут даже и не пахнет отимальным алгоритмом, но в принципе задачка для современного компьютера чересчур легкая... буду работать над оптимальностью дальше, а пока готов к критике
program LuckyTicket;

{$APPTYPE CONSOLE}

uses
  SysUtils;

const
  MinSum = 0;
  MaxSum = 27;

var
    mas: array[MinSum..MaxSum] of Cardinal = (0, 0, 0, 0, 0, 0, 0,
                                              0, 0, 0, 0, 0, 0, 0,
                                              0, 0, 0, 0, 0, 0, 0,
                                              0, 0, 0, 0, 0, 0, 0);
    dig_1, dig_2, dig_3: Byte;     {dig_1,dig_2,dig_3}
    Sum: Cardinal;
    i: Integer;
    
begin
  for dig_1 := 0 to 9 do
    for dig_2 := 0 to 9 do
      for dig_3 := 0 to 9 do
        begin
          Sum := dig_1 + dig_2 + dig_3;
          Inc(mas[Sum])
        end;
  Sum := 0;
  for i := MinSum to MaxSum do
    Sum := Sum + mas[i]*mas[i];
  writeln(Sum);
  Readln;
end.
1 апр 09, 14:39    [7006054]     Ответить | Цитировать Сообщить модератору
 Re: решение тривиальной алгоритмической задачи разными подходами и средствами  [new]
no-cl
Guest
vino
1) асм можно, но крайне не желательно использовать в решениях напрямую - для совместимости с разными платформами. Это к любому процедурному языку относится.
2) 256 элементов мало но эффективно, к тому же никто не мешает написать свою побитовую реализацию - и Pascal, и в C и в др.
3) подмножества любого типа и хранятся с использованием общих конструкций вроде дерева, но и расход памяти другой
4) битовые маски используются для экономии ОП, что важно при обработке огромных потоков данных, при чем тут "грошевое преимущество"? Да и в паскаль его ввели, когда ОП часто не исчислялась даже мегабайтами, чтобы упростить работу с сущностями типа множество. А сейчас, естественно, мало востребовано.

... а по делу - ничего. Пример, где паскалевские множества (8-байтные, это с современном 64-битном мире-то, то есть где всего одно число - уже 64-элементное множество) давали бы не-грошевые преимущества в студию. То что битовые маски и битовые операции не нужны я не утверждал.

vino
Не судите по себе! Возможно, в Вашей работе не требуется пресловутое "мелочное ускорение", так и не надо об этом говорить. А ошибки в архитектуре сейчас, в основном, из-за элементарной безграмотности, а учить теорию лень. Уверен, что низкоуровневый программист чаще уделяет внимание архитектуре и алгоритмам, чем высокоуровневый.
По поводу написанных (часто на коленке) супер-решениях - смотри IMHO.

Извините, но это вы судите по себе. А я сужу по большинству. Это как бы правильнее.
Ошибки в архитектуре имеют множество причин, но даже если архитектура и алгоритмы безупречны, если это все реализуется на низкоуровневом или невыразительном языке (типа васика), то превращается в сложночитаемого и сложноподдерживаемого монстра, что губительно для проекта в целом (а знаете ли, завершенный плохой проект лучше незавершенного "хорошего").
И компетентность программиста в алгоритмах вообще никак не зависит от языка, на котором он программирует - это, как вы заметили предложением раньше, но потом тут же почему-то передумали, целиком и полностью определяется математической грамотностью + опытом. Компетентность в архитектуре определяется, в целом, тем же.

vino
Gluk (Kazan), например, сжатие и эффективная передача данных, программирование приборов с ограниченным объемом памяти или быстродействием. На самом деле очень много задач с ограниченным ресурсом по памяти или по быстродействию. В отличие от сверхдешевых PC, каналы связи и надежные ЭВМ не могут похвастаться излишками ресурсов.

Верно, именно в этих задачах алгоритмы гораздо важнее мелочей реализации. Я даже боюсь предположить, насколько медленнее будет всячески оптимизированное пусть даже под какой-то конкретный процессор и написанное на ассемблере косинусное преобразование "в лоб", чем БДКП на лиспе. Интересно проверить, кстати; мнится мне, это не десятикратное и даже не стократное различие.

vino
Только вот, к сожалению, заданные условия решения нарушены на все 100%

Так как на счет сформулированной мной задачи? "Дана последовательность чисел из K+L элементов. Нужно поменять местами две его части: 0..K-1 и K..K+L-1 за время O(1)."
Пока кроме питона и лиспа тут с ней никто не справился.
1 апр 09, 14:40    [7006059]     Ответить | Цитировать Сообщить модератору
 Re: решение тривиальной алгоритмической задачи разными подходами и средствами  [new]
студентик
Member

Откуда: Альфа Центавра
Сообщений: 294
забыл добавить это вариант решения задачи счастливые билеты
1 апр 09, 14:41    [7006073]     Ответить | Цитировать Сообщить модератору
 Re: решение тривиальной алгоритмической задачи разными подходами и средствами  [new]
студентик
Member

Откуда: Альфа Центавра
Сообщений: 294
no-cl

... а по делу - ничего. Пример, где паскалевские множества (8-байтные, это с современном 64-битном мире-то, то есть где всего одно число - уже 64-элементное множество) давали бы не-грошевые преимущества в студию. То что битовые маски и битовые операции не нужны я не утверждал.

если у вас небольшие перечеслимые множества в пределах 32 элементов(к примеру символы),
паскаль реализут весьма эффективный код по работе с его элементами: включение в множество, проверка на принадлежность и т.п.


vino
Только вот, к сожалению, заданные условия решения нарушены на все 100%

Так как на счет сформулированной мной задачи? "Дана последовательность чисел из K+L элементов. Нужно поменять местами две его части: 0..K-1 и K..K+L-1 за время O(1)."
Пока кроме питона и лиспа тут с ней никто не справился.[/quot]
так уже курьезы пошли...
1 апр 09, 14:49    [7006126]     Ответить | Цитировать Сообщить модератору
 Re: решение тривиальной алгоритмической задачи разными подходами и средствами  [new]
Gluk (Kazan)
Member

Откуда:
Сообщений: 9372
vino
Gluk (Kazan)
Вы этим занимаетесь ?

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


На форуме очень много шума по поводу низкоуровневой оптимизации, но в реальной жизни (по моему опыту) низкоуровневая оптимизация требуется ИСКЛЮЧИТЕЛЬНО редко.
Просто удивляюсь как ВАМ повезло :)

P.S. Мне кстати тоже повезло (но понимания я по этому поводу обычно не нахожу)
1 апр 09, 14:55    [7006162]     Ответить | Цитировать Сообщить модератору
 Re: решение тривиальной алгоритмической задачи разными подходами и средствами  [new]
Gluk (Kazan)
Member

Откуда:
Сообщений: 9372
Кроме того, как справедливо было замечено, алгоритм может дать в разы большую оптимизацию чем экономия на спичках. И чрезвычайно часто на моей памяти, программисты ошибались в оптимальности тех или иных конструкций, а компилятор оказывался ПРАВ.

Я вас прошу, не оптимизируйте преждевременно (c)
1 апр 09, 14:58    [7006184]     Ответить | Цитировать Сообщить модератору
Топик располагается на нескольких страницах: Ctrl  назад   1 2 3 4 5 6 [7] 8 9 10 11 .. 33   вперед  Ctrl
Все форумы / Программирование Ответить