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

Откуда:
Сообщений: 1191
студентик, по контролю эффективности работы кода низкоуровневых задач С, исторически заменивший asm при разработке операционок и сложных и универсальных систем, равных не знаю. Но для создания все усложняющихся программных комплексов не подходит. А вот в востребованных предметных областях давно развиваются ЯВУ и метаязыки (как процедурные так и декларативные типа Пролога), способные эффективно решать именно "свои" задачи. Тот же универсальный Python вобрал в себя лучшее из С и других языков с целью ускорить процесс программирования. Однако, оптимизацию кода там где это нужно - никто не отменяет.
Паскаль, IMHO, остается весьма полезен для обучения, например, процедурному мышлению, для чего он, собственно и создавался. А вот эффективность рабочего кода Object Pascal сомнительна. Также очевидна неэффективность декларативных языков вне своей предметной области.
В задаче темы заданы специфические условия минимализма, убийственные для "интуитивных" алгоритмов и тем более для непроцедурных ЯВУ. Я считаю, что на С приведенный мной алгоритм получится более эффективным, чем в Паскале и в других ЯВУ, а дальнейшая оптимизация - только на asm. Только для чего?
1 апр 09, 15:14    [7006305]     Ответить | Цитировать Сообщить модератору
 Re: решение тривиальной алгоритмической задачи разными подходами и средствами  [new]
no-cl
Guest
студентик
если у вас небольшие перечеслимые множества в пределах 32 элементов(к примеру символы),
паскаль реализут весьма эффективный код по работе с его элементами: включение в множество, проверка на принадлежность и т.п.

Да, у меня часто бывают небольшие перечислимые множества в пределах 32 элементов. Это какие-либо флаги. Работа с ними (добавить-удалить-обратить-объединить-пересечь) лично у меня редко превышает 1 операцию в несколько секунд, так что 5 тактов они выполняются или 500 я даже не могу померить разницу при помощи таймера; но есть конечно задачи где это используется значительно более интенсивно, среди них я еще пока не встречал ни одной задачи, использующей более 32-элементных множеств, вот потому я и спрашиваю про область применения именно паскальских, 256-битных, множеств. Для меня эта "область применения" заключается просто в приятном синтаксисе, не более (но и не менее).
1 апр 09, 15:23    [7006404]     Ответить | Цитировать Сообщить модератору
 Re: решение тривиальной алгоритмической задачи разными подходами и средствами  [new]
студентик
Member

Откуда: Альфа Центавра
Сообщений: 294
vino
студентик, по контролю эффективности работы кода низкоуровневых задач С, исторически заменивший asm при разработке операционок и сложных и универсальных систем, равных не знаю. Но для создания все усложняющихся программных комплексов не подходит. А вот в востребованных предметных областях давно развиваются ЯВУ и метаязыки (как процедурные так и декларативные типа Пролога), способные эффективно решать именно "свои" задачи. Тот же универсальный Python вобрал в себя лучшее из С и других языков с целью ускорить процесс программирования. Однако, оптимизацию кода там где это нужно - никто не отменяет.
Паскаль, IMHO, остается весьма полезен для обучения, например, процедурному мышлению, для чего он, собственно и создавался. А вот эффективность рабочего кода Object Pascal сомнительна. Также очевидна неэффективность декларативных языков вне своей предметной области.
В задаче темы заданы специфические условия минимализма, убийственные для "интуитивных" алгоритмов и тем более для непроцедурных ЯВУ. Я считаю, что на С приведенный мной алгоритм получится более эффективным, чем в Паскале и в других ЯВУ, а дальнейшая оптимизация - только на asm. Только для чего?



для того чтоб оформить в процедуру и положить на полку=) я полностью с тобой согласен, я считаю вся сила кода на С не только в возможностях языка ,а скорее даже в его компиляторе, в сети много писали, что компилятор на С от Майкрософт один из лучших в мире (Windows покрайне мере). В этом легко кстати убедиться. Видел талантливых людей, которые пишут драйвера и различные системные программы, или хотели бы их писать на Паскале, в силу удобности языка, его "ужасной" типизации, за которую поругивают сторонники С, но которая помогает избегать трудноотслеживаемые ошибки. К сожалению последние версии Дельфи уже потеряли былую мощь и актуальны только в РАД программировании и обучении...
1 апр 09, 16:18    [7007037]     Ответить | Цитировать Сообщить модератору
 Re: решение тривиальной алгоритмической задачи разными подходами и средствами  [new]
vino
Member

Откуда:
Сообщений: 1191
no-cl
небольшие перечислимые множества в пределах 32 элементов. Это какие-либо флаги. Работа с ними (добавить-удалить-обратить-объединить-пересечь) лично у меня редко превышает 1 операцию в несколько секунд, так что 5 тактов они выполняются или 500 я даже не могу померить разницу при помощи таймера; но есть конечно задачи где это используется значительно более интенсивно, среди них я еще пока не встречал ни одной задачи, использующей более 32-элементных множеств, вот потому я и спрашиваю про область применения именно паскальских, 256-битных, множеств. Для меня эта "область применения" заключается просто в приятном синтаксисе, не более (но и не менее).

Мне встречались интерфейсные модули для системы реального времени, написаные на паскале вперемежку с асмом, скорость выполнения наиболее важных участков которых расчитана с точностью до единиц тактов, особенно если это внутри каких бы то ни было циклов. И дело не в том, что модуль на паскале тоже использовал флаги (и достаточно эффективно), дело в экономии вычислительных ресурсов, которые важны для других задач системы.
А Вы про "5 тактов они выполняются или 500" ?!
1 апр 09, 16:18    [7007039]     Ответить | Цитировать Сообщить модератору
 Re: решение тривиальной алгоритмической задачи разными подходами и средствами  [new]
vino
Member

Откуда:
Сообщений: 1191
По поводу 32 битного множества: к сожалению, в алфавите больше букв, да еще цифры и др. символы. А старые алгоритмы проверок хорошо себя зарекомендовали, поэтому незачем из-за появления универсальных классов отказываться от простейших процедур проверки ввода символов ANSI и т.п.
Также вспоминается достаточно эффективный маппинг при обработке больших массивов по какому-либо малозначному признаку (вместо индексов) правда на практике используется существенно больше 256 элементов и соответствующая реализация. Правда, на Паскале это уже не так эффективно, как в том же С.
1 апр 09, 16:32    [7007134]     Ответить | Цитировать Сообщить модератору
 Re: решение тривиальной алгоритмической задачи разными подходами и средствами  [new]
Gluk (Kazan)
Member

Откуда:
Сообщений: 9372
vino
no-cl
небольшие перечислимые множества в пределах 32 элементов. Это какие-либо флаги. Работа с ними (добавить-удалить-обратить-объединить-пересечь) лично у меня редко превышает 1 операцию в несколько секунд, так что 5 тактов они выполняются или 500 я даже не могу померить разницу при помощи таймера; но есть конечно задачи где это используется значительно более интенсивно, среди них я еще пока не встречал ни одной задачи, использующей более 32-элементных множеств, вот потому я и спрашиваю про область применения именно паскальских, 256-битных, множеств. Для меня эта "область применения" заключается просто в приятном синтаксисе, не более (но и не менее).

Мне встречались интерфейсные модули для системы реального времени, написаные на паскале вперемежку с асмом, скорость выполнения наиболее важных участков которых расчитана с точностью до единиц тактов, особенно если это внутри каких бы то ни было циклов. И дело не в том, что модуль на паскале тоже использовал флаги (и достаточно эффективно), дело в экономии вычислительных ресурсов, которые важны для других задач системы.
А Вы про "5 тактов они выполняются или 500" ?!


А сколько тактов к примеру занимает переключение контекста ?
Или синхронизация кэша ?
1 апр 09, 16:33    [7007136]     Ответить | Цитировать Сообщить модератору
 Re: решение тривиальной алгоритмической задачи разными подходами и средствами  [new]
no-cl
Guest
vino
Мне встречались интерфейсные модули для системы реального времени, написаные на паскале вперемежку с асмом, скорость выполнения наиболее важных участков которых расчитана с точностью до единиц тактов, особенно если это внутри каких бы то ни было циклов. И дело не в том, что модуль на паскале тоже использовал флаги (и достаточно эффективно), дело в экономии вычислительных ресурсов, которые важны для других задач системы.
А Вы про "5 тактов они выполняются или 500" ?!

Что-то мы на разных языках разговариваем.
Совершенно не убедительно звучат абстрактные фразы про тактики в циклах (которые кстати в системах реального времени должны быть в первую очередь именно рассчитаны, то есть должно гарантироваться максимальное время выполнения (дедлайн), то есть детерминированность первична, а оптимизация вторична; ну а уж если работа с множествами происходит вне циклов, то и в системах реального времени никого волновать не будет - 1000500 тактов программа выполняется или 1000050).
Там использовалось более 32/64 флагов или нет и каково было процентное соотношение операций с множествами к общему количеству операций? Вот что интересно.
1 апр 09, 16:38    [7007174]     Ответить | Цитировать Сообщить модератору
 Re: решение тривиальной алгоритмической задачи разными подходами и средствами  [new]
студентик
Member

Откуда: Альфа Центавра
Сообщений: 294
mayton
Задачка.

Подсчитать количество счастливых билетов. Серия 000000 - 999999.

Решение типа "полный перебор" - не приветствуется.


Господа хотелось бы выслушать ваши предложения, или увидеть ваши программы на функциональных или процедурных языках , или хотя бы критику по поводу вышележащей задачи...
Задача же так и просится быть решенной в Лиспе:) ,или другом языке, приводите свои варианты...
пока вариант на Сикъюл неоптимален
1 апр 09, 16:55    [7007314]     Ответить | Цитировать Сообщить модератору
 Re: решение тривиальной алгоритмической задачи разными подходами и средствами  [new]
Gluk (Kazan)
Member

Откуда:
Сообщений: 9372
студентик
mayton
Задачка.

Подсчитать количество счастливых билетов. Серия 000000 - 999999.

Решение типа "полный перебор" - не приветствуется.


Господа хотелось бы выслушать ваши предложения, или увидеть ваши программы на функциональных или процедурных языках , или хотя бы критику по поводу вышележащей задачи...
Задача же так и просится быть решенной в Лиспе:) ,или другом языке, приводите свои варианты...
пока вариант на Сикъюл неоптимален


К сообщению приложен файл. Размер - 0Kb
1 апр 09, 16:59    [7007347]     Ответить | Цитировать Сообщить модератору
 Re: решение тривиальной алгоритмической задачи разными подходами и средствами  [new]
mayton
Member

Откуда: loopback
Сообщений: 43443
Формула с wikipedia это неинтересно ИМХО. Гораздо интереснее было прослеживать ход рассуждений разработчика. И интересно было находить оригинальные решения.
1 апр 09, 17:29    [7007591]     Ответить | Цитировать Сообщить модератору
 Re: решение тривиальной алгоритмической задачи разными подходами и средствами  [new]
Gluk (Kazan)
Member

Откуда:
Сообщений: 9372
mayton
Формула с wikipedia это неинтересно ИМХО. Гораздо интереснее было прослеживать ход рассуждений разработчика. И интересно было находить оригинальные решения.


Она не с википедии
1 апр 09, 17:54    [7007792]     Ответить | Цитировать Сообщить модератору
 Re: решение тривиальной алгоритмической задачи разными подходами и средствами  [new]
Q
Guest
>>> def sum(a, b):
	return a+b

>>> def mul(a, b):
	return a*b

>>> bb = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 9, 8, 7, 6, 5, 4, 3, 2, 1]
>>> tt = range(19)
>>> dd = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 9, 8, 7, 6, 5, 4, 3, 2, 1]
>>> for digits in range(2,4):
	for i in range(10):
		tt[i] = reduce(sum, map(mul, bb[9-i:], dd[:len(dd)+i-9]))
		tt[18-i]=tt[i]
	dd = tt
	tt = range(19)
	dd[9]
1 апр 09, 18:39    [7008035]     Ответить | Цитировать Сообщить модератору
 Re: решение тривиальной алгоритмической задачи разными подходами и средствами  [new]
MasterZiv
Member

Откуда: Питер
Сообщений: 34548

студентик пишет:

Какую фигню ты тут пишешь ...

> Видел талантливых людей, которые пишут драйвера

> или хотели бы их писать на Паскале, в силу удобности языка,

> .. версии Дельфи ... потеряли былую мощь

Драйвера не пишут талантливые люди. Пишут грамотные и аккуратные.
Паскаль - дебильный мертворождённый язык для студентов, где уж там удобство.
Ну и ДЕЛЬФИ и МОЩЬ -- это вещи несовместимые.

Posted via ActualForum NNTP Server 1.4

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

Откуда: Питер
Сообщений: 34548

студентик пишет:

> Подсчитать количество счастливых билетов. Серия 000000 - 999999.

Так надо именно ПОСЧИТАТЬ КОЛИЧЕСТВО счастливых билетов, или
НАЙТИ ВСЕ СЧАСТЛИВЫЕ БИЛЕТЫ ?

Posted via ActualForum NNTP Server 1.4

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

Откуда: Питер
Сообщений: 34548
Просто ПОСЧИТАТЬ КОЛИЧЕСТВО счастливых билетов -- это аналитическая задача, для неё не надо программу писать.
1 апр 09, 19:07    [7008122]     Ответить | Цитировать Сообщить модератору
 Re: решение тривиальной алгоритмической задачи разными подходами и средствами  [new]
vino
Member

Откуда:
Сообщений: 1191
no-cl
Там использовалось более 32/64 флагов или нет и каково было процентное соотношение операций с множествами к общему количеству операций? Вот что интересно.

Насколько помню, HPFS подразумевает довольно интенсивную работу с битовой маской секторов в 2048 байт на каждые 16384 сектора.
no-cl
Что-то мы на разных языках разговариваем.
Совершенно не убедительно звучат абстрактные фразы про тактики в циклах (которые кстати в системах реального времени должны быть в первую очередь именно рассчитаны, то есть должно гарантироваться максимальное время выполнения (дедлайн), то есть детерминированность первична, а оптимизация вторична; ну а уж если работа с множествами происходит вне циклов, то и в системах реального времени никого волновать не будет - 1000500 тактов программа выполняется или 1000050).

Вот когда "забывают" оптимизировать код работы с потоками данных, тогда и получаются малоприменимые системы, пожирающие ресурсы. Кому нужна, например, система контроля техпроцесса или видеонаблюдения, вываливающаяся в самый неподходящий момент или пропускающая важные подробности из-за элементарной нехватки ресурсов
1 апр 09, 19:23    [7008183]     Ответить | Цитировать Сообщить модератору
 Re: решение тривиальной алгоритмической задачи разными подходами и средствами  [new]
vino
Member

Откуда:
Сообщений: 1191
MasterZiv
Просто ПОСЧИТАТЬ КОЛИЧЕСТВО счастливых билетов -- это аналитическая задача, для неё не надо программу писать.

Интересно, что решение этой задачи на Паскале видел в каком-то задачнике 90х годов.
IMHO, любую задачу нужно анализировать
1 апр 09, 19:28    [7008206]     Ответить | Цитировать Сообщить модератору
 Re: решение тривиальной алгоритмической задачи разными подходами и средствами  [new]
AlexandrPlus
Member

Откуда:
Сообщений: 7887
студентик
mayton
Задачка.

Подсчитать количество счастливых билетов. Серия 000000 - 999999.

Решение типа "полный перебор" - не приветствуется.


Господа хотелось бы выслушать ваши предложения, или увидеть ваши программы на функциональных или процедурных языках , или хотя бы критику по поводу вышележащей задачи...
Задача же так и просится быть решенной в Лиспе:) ,или другом языке, приводите свои варианты...
пока вариант на Сикъюл неоптимален


на питоше такой все тот же детский сад

>>> a, i, b = 0, 0, '000000'
>>> while a <= 999999:
	b = b[len(str(a)):]+str(a)
	if int(b[0])+int(b[1])+int(b[2])==int(b[3])+int(b[4])+int(b[5]): i = i + 1
	a = a + 1
>>> i
56940


не перебор, но линейный просмотр

Наверно возможно как-то хитро, но это уже математическая соображалка (не нуждающаяся в программировании), а не программирование.
1 апр 09, 19:42    [7008255]     Ответить | Цитировать Сообщить модератору
 Re: решение тривиальной алгоритмической задачи разными подходами и средствами  [new]
Q
Guest
Хм, должно быть 55252...
1 апр 09, 19:51    [7008308]     Ответить | Цитировать Сообщить модератору
 Re: решение тривиальной алгоритмической задачи разными подходами и средствами  [new]
Q
Guest
>>> b = '123456'
>>> b[3:]
'456'
1 апр 09, 19:53    [7008316]     Ответить | Цитировать Сообщить модератору
 Re: решение тривиальной алгоритмической задачи разными подходами и средствами  [new]
ИМХ0
Guest
В лотерее количество счастливых билетов и размер выигрыша определяется организаторами.
1 апр 09, 19:59    [7008352]     Ответить | Цитировать Сообщить модератору
 Re: решение тривиальной алгоритмической задачи разными подходами и средствами  [new]
AlexandrPlus
Member

Откуда:
Сообщений: 7887
тьфу (пора домой)
 
>>> a, b, c, i = 0, '000000', '', 0
>>> while a <= 999999:
	c = b[len(str(a)):]+str(a)
	if int(c[0])+int(c[1])+int(c[2])==int(c[3])+int(c[4])+int(c[5]): i = i + 1
	a = a + 1

	
>>> i
55252
1 апр 09, 20:10    [7008395]     Ответить | Цитировать Сообщить модератору
 Re: решение тривиальной алгоритмической задачи разными подходами и средствами  [new]
no-cl
Guest
почти лобовое решение
 
def count_lucky(n):
    sums = dict([])
    for i in xrange(0, 10 ** n):
        s = sum(map(int,str(i)))
        if sums.has_key(s):
            sums[s] += 1
        else:
            sums[s] = 1

    ret = 0
    for s in sums.iterkeys():
        ret += sums[s] ** 2
    return ret

>>> count_lucky(4)
4816030
>>> count_lucky(3)
55252
>>> count_lucky(5)
432457640
>>> count_lucky(6)
39581170420L
первый цикл может (И должен) быть оптимизирован ооочень сильно.
1 апр 09, 20:19    [7008438]     Ответить | Цитировать Сообщить модератору
 Re: решение тривиальной алгоритмической задачи разными подходами и средствами  [new]
no-cl
Guest
no-cl
первый цикл может (И должен) быть оптимизирован ооочень сильно.

например так:
memo = dict([])
def cnt(n,s):
    if s == 0: return 1
    if n == 0: return 0
    if memo.has_key((n,s)): return memo[(n,s)]
    ret = 0
    for i in xrange(0,min(s+1,10)):
        ret += cnt(n-1,s-i)
    memo[(n,s)] = ret
    return ret

def count_lucky(n):
    ret = 0
    for s in xrange(0, 9*n + 1):
        ret += cnt(n,s) ** 2
    return ret
>>> count_lucky(6)
39581170420L
>>> count_lucky(8)
343900019857310L
>>> count_lucky(10)
3081918923741896840L
>>> count_lucky(14)
261046730157780861858821136L
>>> count_lucky(40)
1549907697862929680336583303564541550920867807532198717258856653744296207074760L

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

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

студентик пишет:

Какую фигню ты тут пишешь ...

> Видел талантливых людей, которые пишут драйвера

> или хотели бы их писать на Паскале, в силу удобности языка,

> .. версии Дельфи ... потеряли былую мощь

Драйвера не пишут талантливые люди. Пишут грамотные и аккуратные.
Паскаль - дебильный мертворождённый язык для студентов, где уж там удобство.
Ну и ДЕЛЬФИ и МОЩЬ -- это вещи несовместимые.



Ну талантливые программисты - грамотные и аккуратные(не взаимное следствие), иначе их программы не работали бы. Не в меру категоричная фраза "Паскаль - дебильный мертворождённый язык для студентов" указывает на то, что вы один из "прожженых бойцов" холиваров с просторов инета:) Это прекрасный язык для обучения, он прививает людям навык аккуратно писать программы без языковых ухищрений, чтобы они были понятны даже не профессионалу, а это согласитесь тоже ценное качество. Вообще правильная традиция многих вузов давать изучение основ программирования с Паскаля,а затем переходить на С, чтобы люди не "стреляли себе в ногу".
По мне вся сила С в его обширных библиотеках, в мощных компиляторах, в поддержке широких возможностей, но и Паскаль то же не детская забава. "Ну и ДЕЛЬФИ и МОЩЬ -- это вещи несовместимые." - ну погорячился я, как и вы, что и следует ожидать от модератора форума С++:)
У многих людей предвзятое отношение к Паскалю, но все-таки находятся люди спосбные отстаивать его честь. К примеру Ms-Rem(котрого к сожалению уже нет) талантливый системщик статьи, которого занимали призовые места на wasm.ru, писал свои приложения и на Паскале в том числе. Вообще я был приятно удивлен когда обнаружил, что одна из его программ (обнаружение скрытых процессов) написана... внимание на С, Pascal, Assembler. Вывод для меня нужно уважать все языки - как никак они провернеы временем.
1 апр 09, 20:44    [7008556]     Ответить | Цитировать Сообщить модератору
Топик располагается на нескольких страницах: Ctrl  назад   1 .. 3 4 5 6 7 [8] 9 10 11 12 .. 33   вперед  Ctrl
Все форумы / Программирование Ответить