Можно ли из множества целых составить строку ?

← →
Digitman (2003-07-18 14:09) [40]

> Radionov Alexey

ну что ж, попробуй) ... будем считать, что теперь и я в чемберлены записался))

asm-алгоритм, что я набросал, кстати, тоже "причесать" можно ... не самый опт.вариант это ..

здесь важно что ?
1. вынести перераспределение памяти за пределы циклов,
2. минимизировать в разумных пределах само кол-во влож.циклов (чем линейней алгоритм - тем круче)
3. использовать такие инструкции, которые могут быть обработаны конвейерами параллельно

← →
Serginio (2003-07-18 14:18) [41]

2 (Digitman © (18.07.03 14:09)

Сравни с моим без выделения строк. Интересно что, при пересылки PC^ в регистр, работает еще медленнее.
Интересно на сколько твой алгоритм будет эффективней.

← →
Digitman (2003-07-18 14:48) [42]

> Serginio

твой эксперимент не "чистый").. нарушаешь условия поставленной задачи !) ... строку-то результирующую не формируешь, просто подсчитываешь индексы установленных битов)

← →
vuk (2003-07-18 14:59) [43]

to Digitman:
>попробуй уж что ль тогда и вариант с BitTest-инструкцией, на
>предмет сравнения с иными вариантами (в том или ином виде)
Повторяю свой вопрос. Кто-нибудь код, генерируемый при использовании оператора in смотрел или все-таки нет? :o)

P.S.: Это намёк.

← →
Serginio (2003-07-18 15:06) [44]

На строку уходят все ресурсы (пересылку данных). А смысл именно в алгоритме нахождения состава Set. Которую можно представить как сумму.
Интересна в данном случае оптимизация выборки. И как компилятор генерит код используя регистры. И как добиться от паскалевского кода максимальной оптимизации.

← →
vuk (2003-07-18 15:09) [45]

View->Debug Windows->CPU

← →
Serginio (2003-07-18 15:09) [46]

2 vuk © (18.07.03 14:59) Но алгоритм (Serginio (18.07.03 12:00)) быстрее на 40%, чем In. А это достаточно много.

← →
Digitman (2003-07-18 15:11) [47]

> vuk

смотрел, конечно).. bt в ряде случаев там также генерится .. но не во всех

← →
Radionov Alexey (2003-07-18 15:12) [48]

>vuk © (18.07.03 14:59)
Причем тут этот код?

← →
vuk (2003-07-18 15:18) [49]

to Radionov Alexey:
>Причем тут этот код?
Мне советовали протестировать работу BT. Оператор in именно инструкцию BT и генерирует в приведенном мной примере.

← →
Radionov Alexey (2003-07-18 15:34) [50]

>vuk © (18.07.03 15:18)

Понял :)

Но тормоза - в преобразовании в строку.

← →
vuk (2003-07-18 15:39) [51]

to Radionov Alexey:
>Но тормоза - в преобразовании в строку.
Это да. В принципе простейший StringBuilder (с предварительным выделением памяти и конкатенацией строк через StrMove) пишется за 15 минут. И тормоза уходят.

Кстати, еще один плюс оператора in - контроль типов со стороны компилятора.

← →
Serginio (2003-07-18 16:12) [52]

To (vuk) В данном примере 2.55 миллиардов цикл. Проходит за 5-8 секунд. А одина безобидная конструкция
Inc(Counter,(j shl 5) + i); при вычислении 10 миллионов тормозит на целую секунду. Какие будут тормоза при переводе числа в строку и помещении его в буффер?????

← →
vuk (2003-07-18 16:43) [53]

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

← →
Serginio (2003-07-18 16:54) [54]

2(Vuk) Как ты счтаешь твой алгоритм преобразования числа будет быстрее, чем у Digitman © (18.07.03 12:53). И бутет ли он быстрее Inc(Counter,(j shl 5) + i);??? а это оказывается главный тормоз.
А замена
If (Cardinal(1 shl i) and PC^)<>0 Then
Inc(Counter,(j shl 5) + i);

на

If (md and PC^)<>0 Then
inc(Counter,tt);

md:=md shl 1;
inc(tt);
Дает прирост на 40%
Только за счет более оптимального использования регистров.

← →
vuk (2003-07-18 17:09) [55]

Я просто сказал, где там самый главный тормоз. Он именно в работе менеджера памяти.
А что касается преобразования в строку, то лучше использовать не IntToStr, а Str - оно по скорости эффективнее будет.

← →
default (2003-07-19 11:11) [56]

procedure BitSetToStr_(BitSet: Pointer; Str: PChar); asm // BitSet --> EAX, Str --> EDX PUSH ECX PUSH EDI XOR ECX, ECX MOV EDI, EAX MOV BYTE PTR [EDX], 27h INC EDX @@cycle: BT [EDI], ECX JNC @@continue SHLD AX, CX, 16 CMP AX, 100 JAE @@a99 CMP AX, 10 JAE @@a9 OR AL, 30h MOV BYTE PTR [EDX], AL INC EDX JMP @@fin @@a99: DIV BYTE PTR @@ten OR AH, 30h MOV BYTE PTR [EDX + 2], AH MOVZX AX, AL AAM OR AX, 3030h MOV BYTE PTR [EDX], AH MOV BYTE PTR [EDX + 1], AL ADD EDX, 3 JMP @@fin @@a9: DIV BYTE PTR @@ten OR AX, 3030h MOV WORD PTR [EDX], AX ADD EDX, 2 @@fin: MOV BYTE PTR [EDX], "," INC EDX @@continue: INC ECX CMP ECX, 256 JB @@cycle @@exit: MOV BYTE PTR [EDX - 1], 27h POP EDI POP ECX RET @@ten: DB 10 end; procedure TForm1.Button1Click(Sender: TObject); var S: Set Of Byte; Str: String; begin S := [1, 3, 15, 16, 120, 135, 155, 200, 251, 254, 255]; Str := StringOfChar(" ", 50); BitSetToStr_(@S, PChar(Str)); Caption := Str end;
вот ещё вариант, принцип тот же что и у Digitman-а(что-то оптимальнее на асме трудно придумать,
оптимальнее по идее, а не по реализации имеется ввиду)
при больших циклах разница в скорости достигает - чуть меньше 1.5 секунды
только у Digitman-а ошибка где-то с "круглыми" числами типа 100, 120 и тд и запятая перед первым
числом ненужная ставится...
а на Паскале написать код, чтобы он компилился в код эффективнее этого будет очень сложно,
если возможно...

← →
Radionov Alexey (2003-07-21 07:50) [57]

>Digitman © (18.07.03 14:09)

В среднем в 2.6 раза быстрее твоего кода. Но, опять-таки, очевидно почему :))

Type ShortStr = String[3]; Const ValuesTable: Array[0..255] Of ShortStr = ("0", "1", "2", "3", "4", "5", "6", "7", "8", "9", "10", "11", "12", "13", "14", "15", "16", "17", "18", "19", "20", "21", "22", "23", "24", "25", "26", "27", "28", "29", "30", "31", "32", "33", "34", "35", "36", "37", "38", "39", "40", "41", "42", "43", "44", "45", "46", "47", "48", "49", "50", "51", "52", "53", "54", "55", "56", "57", "58", "59", "60", "61", "62", "63", "64", "65", "66", "67", "68", "69", "70", "71", "72", "73", "74", "75", "76", "77", "78", "79", "80", "81", "82", "83", "84", "85", "86", "87", "88", "89", "90", "91", "92", "93", "94", "95", "96", "97", "98", "99", "100", "101", "102", "103", "104", "105", "106", "107", "108", "109", "110", "111", "112", "113", "114", "115", "116", "117", "118", "119", "120", "121", "122", "123", "124", "125", "126", "127", "128", "129", "130", "131", "132", "133", "134", "135", "136", "137", "138", "139", "140", "141", "142", "143", "144", "145", "146", "147", "148", "149", "150", "151", "152", "153", "154", "155", "156", "157", "158", "159", "160", "161", "162", "163", "164", "165", "166", "167", "168", "169", "170", "171", "172", "173", "174", "175", "176", "177", "178", "179", "180", "181", "182", "183", "184", "185", "186", "187", "188", "189", "190", "191", "192", "193", "194", "195", "196", "197", "198", "199", "200", "201", "202", "203", "204", "205", "206", "207", "208", "209", "210", "211", "212", "213", "214", "215", "216", "217", "218", "219", "220", "221", "222", "223", "224", "225", "226", "227", "228", "229", "230", "231", "232", "233", "234", "235", "236", "237", "238", "239", "240", "241", "242", "243", "244", "245", "246", "247", "248", "249", "250", "251", "252", "253", "254", "255"); function BSTS(Const BytesSet : TBytesSet; Res:Pchar):Integer; register; asm push esi push edi push ebx push ebp push edx mov esi,BytesSet mov edi,Res mov edx,-1 @next: mov ecx,32 @skip: mov eax,[esi] test eax,eax jne @loop add edx,32 add esi,4 cmp edx,255 jnl @exit jmp @skip @loop: shr eax,1 inc edx jnc @nSet mov ebx,dword ptr ValuesTable[4*edx] movzx ebp,bl shr ebx,8 mov [edi],ebx add edi,ebp mov byte ptr [edi],"," inc edi @nSet: loop @loop add esi,4 cmp edx,255 jl @next @exit: pop eax pop ebp sub eax,edi pop ebx je @stop neg eax dec eax @stop: pop edi pop esi end; Function RAByteSetToStr(Const Value: TBytesSet): String; Begin Result := StringOfChar(" ", 1026); SetLength(Result,BSTS(Value, PChar(Result))); End;

← →
Radionov Alexey (2003-07-21 10:56) [58]

← →
Radionov Alexey (2003-07-23 10:13) [59]

ОЙ!
Ошибся веткой. Завиняйте...

← →
Radionov Alexey (2003-07-23 10:14) [60]

Удалось чуток ускорить за счет переделки засылки в результат.

mov ebx,dword ptr ValuesTable[4*edx]
movzx ebp,bl
shr ebx,8
mov [edi],ebx
mov byte ptr [edi+ebp],","
lea edi,[edi+ebp+1]

PS
Что-то чемберлены потеряли интерес к этой игрушке-безделушке...

Можно ли из множества целых составить строку ? Найти похожие ветки