Magic Strings Time Out

Във форума е въведено ограничение, което позволява на потребителите единствено да разглеждат публикуваните въпроси.

Hristo_Penchev 389 Точки

Magic Strings Time Out

Здравейте колеги,

Пускам за тестове задачата Magic Strings на C# и се дъня с времето. От 16 теста 13 ми излизът извън времевия лимит. Четох във форума, че е имало проблем с тайминга при джава и допускам, че може да съществува същия и при С#. Или пък моето решение да е прекалено тежко.

Тук можете да го погледнете:
http://pastebin.com/sCnvmfi3

Ползвам осем цикъл с по четири елемента един в друг. Това предполага над 1000 комбинации, не знам това много ли е. За проверките използвам два временни масива и лист от стрингове, който после сортирам. Но доколкото знам тези елементи не са натоварващи. Необходимо ли е да оптимизирам програмата си и как може да стане?

Тагове:

-1

22/06/2014 08:23:45 Programming Basics

mihayloff14 824 Точки

Проблемът на кода ти е, че на всяка част от задачата генерираш 8 цикъла, когато може да няма смисъл. Тоест, съветвам те да обхожваш първите 4 цикъла и ако те са с подходящи стойности.

Ако числата + diff <= 20 (максималната възможна стойност на числата)

Ако числата - diff >= 4 (минималната възможна стойност на числата)

Когато едно от тези две условия е изпълнено, тогава обхождай останалите 4 цикъла, за да спестиш време като при единия случай втората серия числа трябва да имат стойност (първа серия числа + diff) или (първа серия числа - diff).

Ето шаблон: ЛИНК

Вместо да доизмислям задачата, ще те оставя сам да я довършиш, защото едва ли подходът ни би бил един и същ, а освен това бих ти отнел цялото удоволствие от решаването на задачата.

22/06/2014 10:05:04

Hristo_Penchev 389 Точки

Благодаря ти за отговора. Въведох лимит (Сборът между първите четири числа - diff) да бъде между 4 и 20 като абсолютна стойност. Така орязах голяма част от допълнителното циклене, но таймингът не мръдна дори малко. Явно нещо друго ми спъва програмата и я прави бавна. Но не знам какво - масиви, листове?

22/06/2014 16:10:11

Hristo_Penchev 389 Точки

След многобройни тестове в Judge системата открих къде е проблемът. Всъщност осемте цикъла отнемат съвсем малко време. Това, което дъни работата е:

for (byte j = 0; j < sequences.Count; j++) Console.WriteLine(sequences[j]);

Листът sequences е съставен от стрингове. Явно обхождането на лист с референтни типове е доста бавно. Затова предприех друг подход. Махнах листа и заложих азбучната подредба в самите цикли. Това стана много лесно - в началния съхраняващ масив размених местата на цифрите и вместо първоначалното {3, 4, 1, 5} го направих { 1, 4, 5, 3} Така програмата цикли през "теглото" на буквите в азбучен ред и като засече комбинация, която да отговаря на условието, просто я печата, без да товари паметта. Лесно се добавя един булев израз, който да засече дали има изобщо намерени такива числа и ако няма, да връща "No". Тук можете да видите ъпдейтнатия код:

http://pastebin.com/MjZyNBfv

24/06/2014 21:49:45