VPF::Разбитие целого числа на цифры.

diadiavova

Дата 8.2.2009, 21:18 (ссылка)

(нет голосов)

Загрузка ...

Доктор Зло(диагност, настоящий, с лицензией и полномочиями)

Профиль
Группа: Модератор
Сообщений: 5821
Регистрация: 14.8.2008
Где: В Коньфпольте

Репутация: 31
Всего: 142

Не надо передёргивать. Мы обсуждали вопрос о том, что проглотит меньше ресурсов. Тест был исключительно на эту тему. Первоначально ты мне доказывал, что преобразование в число "дешевле", теперь - откуда ни возьмись, нарисовался препод.
"string buf" я передаю только потому, что с самого начала так сделал. В этом и состояла моя идея. И студия тут ни при чём - там есть бинарник.

--------------------

Хочешь получить мудрый совет - читай подписи участников форумов.
Злой доктор Щасзаболит smile

Veon

Дата 8.2.2009, 22:18 (ссылка)

(нет голосов)

Загрузка ...

Новичок

Профиль
Группа: Участник
Сообщений: 11
Регистрация: 27.2.2007

Репутация: нет
Всего: нет

Ужасный тест smile

Для единичного случая намного лучше подходи то, что написал PashaPash. Если уж ты хочешь обрабатывать большое кол-во строк, то есть намного лучше способы чем этот case smile

Кое-чего поправил, чтобы более обьективно было

Убрал

Код


while (!sr.EndOfStream)
{}            {

Лучше тест проводить на готовом массиве строк.

Твоя прога с исправлениями (3-й способ работает только для положительных, можно его выкинуть)

Код


using System;
using System.Collections.Generic;
using System.Text;
using System.IO;
using System.Text.RegularExpressions;
namespace AlgTest
{
    class Program
    {
        private static bool[] chars = new bool[255];
        private static int[] chars1 = new int[255];
        private static int[] chars2 = new int[255];

        static void Main(string[] args)
        {
            string fn = "source.txt";
            StreamReader sr = new StreamReader(fn);

            string[] arr = sr.ReadToEnd().Split(new string[] { "\r\n" }, StringSplitOptions.None);
            sr.Close();

            DateTime startAlg1 = DateTime.Now;
            foreach (string value in arr)
            {
                Alg1(value);
            }
            DateTime endAlg1 = DateTime.Now;

            DateTime startAlg2 = DateTime.Now;
            foreach (string value in arr)
            {
                Alg2(value);
            }
            DateTime endAlg2 = DateTime.Now;

            //new alg
            chars['1'] = false;
            chars['3'] = false;
            chars['5'] = false;
            chars['7'] = false;
            chars['9'] = false;
            chars['0'] = true;
            chars['2'] = true;
            chars['4'] = true;
            chars['6'] = true;
            chars['8'] = true;

            DateTime startAlg3 = DateTime.Now;
            foreach (string value in arr)
            {
                Alg3(value);
            }
            DateTime endAlg3 = DateTime.Now;

            //new alg2
            chars1['1'] = 100;
            chars1['3'] = 100;
            chars1['5'] = 100;
            chars1['7'] = 100;
            chars1['9'] = 100;
            chars1['0'] = 1;
            chars1['2'] = 1;
            chars1['4'] = 1;
            chars1['6'] = 1;
            chars1['8'] = 1;

            DateTime startAlg4 = DateTime.Now;
            foreach (string value in arr)
            {
                Alg4(value);
            }
            DateTime endAlg4 = DateTime.Now;
            sr.Close();



            TimeSpan a1 = endAlg1.Subtract(startAlg1);
            TimeSpan a2 = endAlg2.Subtract(startAlg2);
            TimeSpan a3 = endAlg3.Subtract(startAlg3);
            TimeSpan a4 = endAlg4.Subtract(startAlg4);

            Console.WriteLine("Время затраченное на выполнение алгоритма без преобразования в число");
            Console.WriteLine(a1.Milliseconds.ToString());
            Console.WriteLine("Время затраченное на выполнение алгоритма с преобразованием в число");
            Console.WriteLine(a2.Milliseconds.ToString());
            Console.WriteLine("Время затраченное на alg3");
            Console.WriteLine(a3.Milliseconds.ToString());
            Console.WriteLine("Время затраченное на alg4");
            Console.WriteLine(a4.Milliseconds.ToString());

            Console.ReadLine();
        }

        static void Alg4(string buf)
        {
            int z = 0;
            int a = 0;
            int b = 0;
            foreach (char q in buf)
            {
                z += chars1[q];
            }
            a = z / 100;
            b = z % 100;
        }

        static void Alg3(string buf)
        {
            int a = 0;
            int b = 0;
            foreach (char q in buf)
            {
                if (chars[q])
                    a++;
                else
                    b++;
            }
        }


        static void Alg1(string buf)
        {
            int a = 0;
            int b = 0;
            System.Collections.IEnumerator en = buf.GetEnumerator();
            while (en.MoveNext())
            {
                char cur = (char)en.Current;
                switch (cur)
                {
                    case '0':
                    case '2':
                    case '4':
                    case '6':
                    case '8':
                        a++;
                        break;
                    case '1':
                    case '3':
                    case '5':
                    case '7':
                    case '9':
                        b++;
                        break;
                }
            };
        }

        static void Alg2(string buf)
        {
            int i = int.Parse(buf);
            int a = 0;
            int b = 0;
            do
            {
                int rem;
                i = Math.DivRem(i, 10, out rem);
                if (rem % 2 == 0)
                {
                    a++;
                }
                else
                {
                    b++;
                }
            }
            while (i != 0);
        }

        static void createFile()
        {
            Random r = new Random();
            string fn = "source.txt";

            List<string> qq = new List<string>();

            for (int i = 0; i < 1000000; i++)
            {
                qq.Add(r.Next(-1000000, 1000000).ToString());
            }
            File.WriteAllText(fn, String.Join("\r\n", qq.ToArray()));
        }
    }
}

Да, еще попробовал как оно работает на 1кк строк, после вызова твоего createFile немного офигел smile

Запаришься ждать столько времени с твоими s+=
И проводи тесты лучше в release smile

Зы: мои результаты
Время затраченное на выполнение алгоритма без преобразования в число
196
Время затраченное на выполнение алгоритма с преобразованием в число
227
Время затраченное на alg3
17
Время затраченное на alg4
17

Хотя если в твоем методе с case поправить на

Код


            foreach (char cur in buf)

выдает 14

Это сообщение отредактировал(а) Veon - 8.2.2009, 22:31

diadiavova

Дата 9.2.2009, 01:38 (ссылка)

(нет голосов)

Загрузка ...

Доктор Зло(диагност, настоящий, с лицензией и полномочиями)

Профиль
Группа: Модератор
Сообщений: 5821
Регистрация: 14.8.2008
Где: В Коньфпольте

Репутация: 31
Всего: 142

Цитата(Veon @ 8.2.2009, 22:18

)

Убрал

while (!sr.EndOfStream)
{}

Это зря, оно как бы подразумевалось, забивать все данные в память не всегда целесообразно.

Относительно метода CreateFile делать его идеальным я не собирался, потому, что в программе он не используется, написан на скорую руку, вызван единственный раз. Сделал своё дело и свободен. Оставил я его только для сведения о том, как был сформирован файл.

При замене энумератора форичем код действительно работает быстрее(не знал).

Твои алгоритмы действительно показывают лучшие результаты.

Тест надо запускать несколько раз, поскольк результаты могут отличаться. Идеальным вариантом было бы прогнать по каждому алгоритму несколько раз и выводить усреднённые значения, хотя...и так всё видно.

Кроме того: в качестве результата выводятся только миллисекунды, но если запустить тест на слабой машине могут и секунды возникнуть , а учтены они не будут(это я так на всякий случай).
вместо a1.Milliseconds.ToString() надо писать a1.ToString(). Это для полноты картины.

В любом случае, в контексте темы, вывод один...

--------------------

Хочешь получить мудрый совет - читай подписи участников форумов.
Злой доктор Щасзаболит smile

PashaPash

Дата 9.2.2009, 02:17 (ссылка)

(нет голосов)

Загрузка ...

Эксперт

Профиль
Группа: Завсегдатай
Сообщений: 1233
Регистрация: 3.1.2008

Репутация: 13
Всего: 49

Цитата(diadiavova @ 8.2.2009, 21:18

)

Не надо передергивать. Я сказал про преобразование каждого символа в число vs деление. Прогони свой первоначальный вариант smile

Вырезать такой ляп и начать сравнивать - не честно smile

Цитата(diadiavova @ 9.2.2009, 01:38

)

В любом случае, в контексте темы, вывод один...

Какой?

И, кстати, DateTime+TimeSpan => System.Diagnostics.Stopwatch.

--------------------

Bird's-eye View?

diadiavova

Дата 9.2.2009, 11:24 (ссылка)

(нет голосов)

Загрузка ...

Доктор Зло(диагност, настоящий, с лицензией и полномочиями)

Профиль
Группа: Модератор
Сообщений: 5821
Регистрация: 14.8.2008
Где: В Коньфпольте

Репутация: 31
Всего: 142

Цитата(PashaPash @ 9.2.2009, 02:17

)

Не надо передергивать. Я сказал про преобразование каждого символа в число vs деление. Прогони свой первоначальный вариант smile Вырезать такой ляп и начать сравнивать - не честно

Не надо передёргивать: мой первоначальный вариант подвергся критике по совершенно другому поводу.

Цитата(PashaPash @ 6.2.2009, 16:59

)

Считать четные/нечетные цифры преобразованием числа в строку - это позор.

Далее, после уточнения, что я этого не делаю(здесь ты просто пропёрся, по этому поводу претензий нет - со всеми бывает) ты заявил следующее

Цитата(PashaPash @ 6.2.2009, 17:21

)

Ты работаешь со строковым представлением числа.

И дальнейший спор развивался в контексте вопроса, что в данном случае лучше - преобразование в число или работа со строкой. И кстати: я не понял, ты уже не споришь с тем, что в данном конкретном случае лучше обрабатывать строку непосредственно? smile

Идея со свитчкейсом была с самого начала, просто в шарпе она не очень удобная, из-за этого я сократил малость(я же не думал, что мой код будет рассматриваться под микроскопом).
Код

Код


               switch (cur)
                {
                    case '0':
                    case '2':
                    case '4':
                    case '6':
                    case '8':
                        a++;
                        break;
                    case '1':
                    case '3':
                    case '5':
                    case '7':
                    case '9':
                        b++;
                        break;
                }

На васике выглядит так

Код


Select Case buf
    Case "0"c," 2"c, "4"c, "6"c, "8"c
        a+=1
    Case "1"c," 3"c, "5"c, "7"c, "9"c
        b+=1
End Select

То бишь - 2 инструкции кейс вместо 10.

Цитата(PashaPash @ 9.2.2009, 02:17

)

Какой?

По-моему мы говорили о скорости работы алгоритмов.

Цитата(PashaPash @ 9.2.2009, 02:17

)

И, кстати, DateTime+TimeSpan => System.Diagnostics.Stopwatch.

А это ты к чему?

Это сообщение отредактировал(а) diadiavova - 9.2.2009, 11:31

--------------------

Хочешь получить мудрый совет - читай подписи участников форумов.
Злой доктор Щасзаболит smile

PashaPash

Дата 9.2.2009, 11:42 (ссылка)

(нет голосов)

Загрузка ...

Эксперт

Профиль
Группа: Завсегдатай
Сообщений: 1233
Регистрация: 3.1.2008

Репутация: 13
Всего: 49

Цитата(diadiavova @ 9.2.2009, 11:24

)

Не надо передёргивать: мой первоначальный вариант подвергся критике по совершенно другому поводу.

Цитата(diadiavova @ 9.2.2009, 11:24

)

По-моему мы говорили о скорости работы алгоритмов.

отдельно о скорости, обычно об общем подходе.О скорости:

Цитата(PashaPash @ 6.2.2009, 20:49

)

Проще и дешевле??? С каких это пор преобразование строки в число (для каждого символа) стало проще и дешевле деления на 10 - одной процессорной инструкции? smile)

Вроде бы спор о производительности я утверждал только вот это.
И первоначальный вариант я критиковал именно за "двойное преобразование". Точнее, за цепочку "уже готовый string->int игнорируется"->"возврат к строке"->"ручной энумератор"->"боксинг/анбоксинг"->"преобразование char в string (посимвольное)"->"преобразование string->int (посимвольно)". Видишь тут аж 5 (!) кастов каждого символа? А можно было сделать всего один, и обойтись делением.

Цитата(diadiavova @ 9.2.2009, 11:24

)

В данном конкретном случае это явно задача с каких нибудь курсов. И цель ее явно не научить перебирать символы в строке, а научить работать с целыми числами, делить с остатком и проверять четность. Задачи "найти количество символов 0 2 4 6 8 и 1 3 5 7 9" формулируются обычно совсем по-другому.

Мой вывод - если человека раздразнить - он вылижет совй код smile

)

Добавлено через 43 секунды

Цитата(diadiavova @ 9.2.2009, 11:24

)

И, кстати, DateTime+TimeSpan => System.Diagnostics.Stopwatch.

А это ты к чему?

Это класс специально для меряния временем.

--------------------

Bird's-eye View?

Veon

Дата 9.2.2009, 11:46 (ссылка)

(нет голосов)

Загрузка ...

Новичок

Профиль
Группа: Участник
Сообщений: 11
Регистрация: 27.2.2007

Репутация: нет
Всего: нет

Ну вообще-то задача звучала так "Есть целое число, которое мы вводим с клавиатуры. И необходимо узнать сколько в этом числе нечетных и четных цифр. "
В стандартном методе PashaPash как раз таки работают с числами, вставить туда TryParse и вообще будет хорошо.
diadiavova же считает в строке количество символов '0', '1'... Проглотит число qqq1aaa?

Цитата(diadiavova @ 8.2.2009, 23:38

)

Твои алгоритмы действительно показывают лучшие результаты.

На моей машине 9 case работают быстрее чем с массивами. Я думал что будет наоборот.
Пример с массивами я приводил только чтобы показать, что есть методы быстрее твоего (ошибся и не привел smile

).

А ты занимаешься преждевременной оптимизацией.
Мало того что нет таких сферических прог в которых нужно обрабатывать миллионы строк, так в 1-й раз ты парсил каждую цифру, а во второй использовал Enumerator. Вести спор о ресурсах и скорости вычисления, когда за 10 секунд можно набрасать метод работающий аналогично твоему (не PashaPash), но в 10 раз быстрее smile

Блин, пока писал уже то-же самое ответили smile

Это сообщение отредактировал(а) Veon - 9.2.2009, 11:47

diadiavova

Дата 9.2.2009, 12:44 (ссылка)

(нет голосов)

Загрузка ...

Доктор Зло(диагност, настоящий, с лицензией и полномочиями)

Профиль
Группа: Модератор
Сообщений: 5821
Регистрация: 14.8.2008
Где: В Коньфпольте

Репутация: 31
Всего: 142

Цитата(PashaPash @ 9.2.2009, 11:42

)

отдельно о скорости, обычно об общем подходе.

Для того, чтобы обсуждать общий подход, надо определиться для начала с критериями оценки оновго подхода.

Цитата(PashaPash @ 9.2.2009, 11:42

)

string->int игнорируется"

Я скопипастил исходный пример и исправлял его. Учитывая, что я применил другой подход, исправлять надо было более радикально. При дальнейшем обсуждении я написал, что в число преобразовывать вообще н следовало и мы это обсуждали.

Цитата(PashaPash @ 9.2.2009, 11:42

)

"возврат к строке"

Возврата не было, я просто проигнорировал преобразованное число, ещё раз повторяю, что если бы я сам писал код с самого начала, то строку вообще не парсил бы.

Цитата(PashaPash @ 9.2.2009, 11:42

)

"ручной энумератор"

Здесь согласен(учитывая результаты теста).

Цитата(PashaPash @ 9.2.2009, 11:42

)

"преобразование char в string (посимвольное)"

Здесь тоже спорить не буду, хотя твой "праведный гнев" был направлен совсем в другую сторону.
Возникает интересная ситуация: первоначально ты критикуешь непосредственную работу со строкой, потом, когда выясняется, что критика была неуместной, начинаешь придираться к деталям, возникшим вследствие того, что код писался "не на выставку".

Цитата(PashaPash @ 9.2.2009, 11:42

)

Вроде бы спор о производительности я утверждал только вот это.

Да нет, ещё и вот это как бы имеет отношение к делу

Цитата(PashaPash @ 6.2.2009, 20:49

)

Это большой недочет. Попытка исправления его подвинет алгортм на один шаг в сторону спагетти. Уверен, ты понимаешь сколько стоит выловить такой "недочет" в системе средних размеров.

Напомню: речь шла о "падении на отрицательных". Куда подвинула попытка его исправления мы видели - алгоритм заработал быстрее.

Цитата(PashaPash @ 9.2.2009, 11:42

)

Цитата(PashaPash @ 9.2.2009, 11:42

)

Возможно, только

Цитата(PashaPash @ 6.2.2009, 18:53

)

В условии написано - целых чисел. Отрицательные натуральные - это целые. Условие уже поставлено, так что отрицательные числа имеют к задаче вполне конкретное отношение smile А про проверку корректности в условии ничего нет.

Раз ты так уж уповаешь на условия, то давай не будем от них отступать. В условии шла речь о решении конкретной задачи, а не о способе её решения.

Цитата(PashaPash @ 9.2.2009, 11:42

)

Мой вывод - если человека раздразнить - он вылижет совй код

Для того, чтобы "вылизать" код надо, как минимум знатькак это сделать. Вся фишка в том, что общую концепцию я не изменил при "вылизывании". Я всё равно обрабатываю строку непосредственно и алгоритм работает быстрее твого smile

Цитата(Veon @ 9.2.2009, 11:46

)

В программу число попадает в виде текста, в этом вся суть. Если бы исходные данные были числовыми, то и разговор был бы другим. В процессе обсуддения уже звучала мысль, что в условии речи о валидации не шло(то бишь: предполагается, что данные вводятся корректно), если требуется валидация, то и расклад(опять-таки) другой.
Проверка данных - процедура недешёвая. Если исходить из предположения, что данные вводятся корректно, то выполнять её - расточительство.

Цитата(Veon @ 9.2.2009, 11:46

)

Мало того что нет таких сферических прог в которых нужно обрабатывать миллионы строк, так в 1-й раз ты парсил каждую цифру, а во второй использовал Enumerator. Вести спор о ресурсах и скорости вычисления, когда за 10 секунд можно набрасать метод работающий аналогично твоему (не PashaPash), но в 10 раз быстрее

В 10 раз - это ты загнул.

И потом: чо вы все до этого злощастного энумератора докопались, ну тормозит он малость, но даже с ним работает быстрее.
smile

--------------------

Хочешь получить мудрый совет - читай подписи участников форумов.
Злой доктор Щасзаболит smile

diadiavova

Дата 9.2.2009, 12:44 (ссылка)

(нет голосов)

Загрузка ...

Доктор Зло(диагност, настоящий, с лицензией и полномочиями)

Профиль
Группа: Модератор
Сообщений: 5821
Регистрация: 14.8.2008
Где: В Коньфпольте

Репутация: 31
Всего: 142

Чойт опять сообщение дублируется

Это сообщение отредактировал(а) diadiavova - 9.2.2009, 12:49

--------------------

Хочешь получить мудрый совет - читай подписи участников форумов.
Злой доктор Щасзаболит smile

Veon

Дата 9.2.2009, 12:56 (ссылка)

(нет голосов)

Загрузка ...

Новичок

Профиль
Группа: Участник
Сообщений: 11
Регистрация: 27.2.2007

Репутация: нет
Всего: нет

Цитата(diadiavova @ 9.2.2009, 10:44

)

В 10 раз - это ты загнул.

Цитата(Veon @ 8.2.2009, 20:18

)

Время затраченное на выполнение алгоритма без преобразования в число
196
Время затраченное на выполнение алгоритма с преобразованием в число
227
Время затраченное на alg3
17
Время затраченное на alg4
17

Да, загнул, в 11.5 раз
А учитывая foreach с case - в 14 smile

Хм, на рабочей машине результаты другие, метод с массивами в 3 раза быстрее метода с 9 case.

Это сообщение отредактировал(а) Veon - 9.2.2009, 13:45

PashaPash

Дата 9.2.2009, 14:21 (ссылка)

(голосов:2)

Загрузка ...

Эксперт

Профиль
Группа: Завсегдатай
Сообщений: 1233
Регистрация: 3.1.2008

Репутация: 13
Всего: 49

diadiavova, да ладно отпираться, просто признайся что написал кривой код - и мы от тебя отстанем smile

Это сообщение отредактировал(а) PashaPash - 9.2.2009, 14:21

--------------------

Bird's-eye View?

diadiavova

Дата 9.2.2009, 15:54 (ссылка)

(нет голосов)

Загрузка ...

Доктор Зло(диагност, настоящий, с лицензией и полномочиями)

Профиль
Группа: Модератор
Сообщений: 5821
Регистрация: 14.8.2008
Где: В Коньфпольте

Репутация: 31
Всего: 142

Veon, На моей машине после замены энумератора форичем время на выполнение сократилось в ~1,5 раза.

PashaPash, А дело не в коде, а в подходе к решению конкретной задачи. Ты используешь шаблонный подход со стандартными алгоритмами, а я подхожу к вопросу более гибко smile

Цитата

Гибше надо быть. А на вещи смотреть - ширше.

Это сообщение отредактировал(а) diadiavova - 9.2.2009, 15:55

--------------------

Хочешь получить мудрый совет - читай подписи участников форумов.
Злой доктор Щасзаболит smile

diadiavova

Дата 9.2.2009, 16:38 (ссылка)

(нет голосов)

Загрузка ...

Доктор Зло(диагност, настоящий, с лицензией и полномочиями)

Профиль
Группа: Модератор
Сообщений: 5821
Регистрация: 14.8.2008
Где: В Коньфпольте

Репутация: 31
Всего: 142

Проверил первоначальный код. Парсить по одному символу(предварительно преобразовав в строку) - идея действительно плохая(признаю smile

) нашёл другой выход

Код


        static void Main(string[] args)
        {
            string buf;
            Console.WriteLine("Введите целое число");
            buf = Console.ReadLine();
            int a = 0;
            int b = 0;
          foreach (char ch in buf)
            {
        if (ch == '-') { continue; }
        int cur = ch - '0';
                if (cur % 2 == 0)
                {
                    a++;
                }
                else
                {
                    b++;
                };
            };
            Console.WriteLine("Количество четных цифр " + a.ToString() + " в числе " + buf);
            Console.WriteLine("Количество не четных цифр " + b.ToString() + " в числе " + buf);
            Console.ReadLine();
        }

--------------------

Хочешь получить мудрый совет - читай подписи участников форумов.
Злой доктор Щасзаболит smile

Partizan

Дата 9.2.2009, 16:45 (ссылка)

(нет голосов)

Загрузка ...

Let's do some .NET

Профиль
Группа: Модератор
Сообщений: 2828
Регистрация: 19.12.2005
Где: Санкт-Петербург

Репутация: 18
Всего: 67

diadiavova, проверьте на числе "---------" ;)

--------------------

СУВ,
Partizan.

diadiavova

Дата 9.2.2009, 16:47 (ссылка)

(нет голосов)

Загрузка ...

Доктор Зло(диагност, настоящий, с лицензией и полномочиями)

Профиль
Группа: Модератор
Сообщений: 5821
Регистрация: 14.8.2008
Где: В Коньфпольте

Репутация: 31
Всего: 142

Да, как бы, обсуждали это уже несколько раз. Изначально условились исходить из того, что вводимые данные корректны.

--------------------

Хочешь получить мудрый совет - читай подписи участников форумов.
Злой доктор Щасзаболит smile

0 Пользователей читают эту тему (0 Гостей и 0 Скрытых Пользователей)
0 Пользователей:
« Предыдущая тема \| Общие вопросы по .NET и C# \| Следующая тема »