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

← →
Альф (2003-07-17 16:11) [0]

Например есть MySet: set of byte = [3, 8, 12];
надо получить строчку "3, 8, 12".
Можно ли как то это сделать, кроме как прохода по всему диапазону множества ???
Пока вижу только один путь: цикл по диапазону [byte] c проверкой
if i in MySet then s := s + intToStr(i);

← →
Palladin (2003-07-17 16:17) [1]

только так, больше никак...

← →
Digitman (2003-07-17 16:32) [2]

> Palladin

ну эт ты загнул)

если бы инспектор объектов так поступал, "тормоза" были бы, думаю, ощутимые в некоторых случаях

> Альф

var ByteSet: set of byte = [3, 8, 12]; procedure TfrmMain.Button1Click(Sender: TObject); var i: Integer; idx: Integer; mask: Byte; s: string; begin s := #39; for i := 0 to 255 do begin mask := 1 shl (i mod 8); idx := i div 8; if Boolean(PByteArray(@ByteSet)[idx] and mask) then begin if Length(s) > 1 then s := s + ","; s := s + IntToStr(i); end; end; s := s + #39; showmessage(s); end;

← →
Digitman (2003-07-17 16:35) [3]

конечно, инспектор не так делает, вместо этого он использует инструкцию BitTest

← →
Palladin (2003-07-17 16:35) [4]

мда... с множествами стараюсь не работать...

но в копилку прибавил :)

← →
Skier (2003-07-17 16:38) [5]

>Digitman © (17.07.03 16:32)
А взятие адреса не нужно ?
if Boolean(PByteArray(@ByteSet) ^[idx] and mask) then

← →
Digitman (2003-07-17 16:38) [6]

> Palladin

так ведь множество - это просто массив байт) ... состояние каждого бита которого в конкретных позициях и дает оператору IN информацию о присутствующем эл-те множества

← →
Digitman (2003-07-17 16:40) [7]

> Skier

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

← →
Palladin (2003-07-17 16:43) [8]

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

← →
Digitman (2003-07-17 16:53) [9]

> Palladin

ну как же ? а BitArray ? та же работа с множеством по сути ! неужто и BitArray не используешь ни в коем виде ?

← →
Serginio (2003-07-17 17:01) [10]

2 Digitman а тебе не кажется, что по тому же алгоритму и работает IN???
Просто Set был придуман для упрощения операция побитового сравнения и минимизации массива данных.
И если есть разница в скорости не мог бы ты ее привести.

← →
Digitman (2003-07-17 17:11) [11]

> Serginio

а я разве возражаю ?) разумеется, по тому же алгоритму ! просто IN не оптимизирован для производительного решения задачи по сабжу. Приведенный мной алгоритм тоже не претендует на оптимальность, это просто как возражение фразе "больше никак")

← →
Serginio (2003-07-17 17:17) [12]

Может так быстрее будет???
procedure TfrmMain.Button1Click(Sender: TObject);
var
i: Integer;
idx: PInteger;
mask: Byte;
s: string;
begin
s := #39;
idx:=@ByteSet;
if (1 and idx^)>0 Then
s := s + IntToStr(i);

for i := 1 to 255 do
begin
If (i mod 32)=0 Then
inc(idx);
mask := 1 shl (i mod 32);

if Boolean(idx^ and mask)) then
begin
if Length(s) > 1 then
s := s + ",";
s := s + IntToStr(i);
end;
end;
s := s + #39;
showmessage(s);
end;

← →
Digitman (2003-07-17 17:28) [13]

оптимальней всего, думаю, будет ключевой asm-блок, где смещения бита устанавливается цикл.инкрементом регистра INC REG32, и здесь же следом BT MEM, REG32

← →
Serginio (2003-07-17 17:29) [14]

Согласен.

← →
Palladin (2003-07-17 17:31) [15]

> Digitman © (17.07.03 16:53)

BitArray это всмысле рассматривание некоего участка памяти как массив битов?
в этом смысле конечно, хотя не часто, но случается...

← →
Digitman (2003-07-17 17:44) [16]

> Palladin

ну дык !) то же множество, но - проктологически)

← →
Palladin (2003-07-17 17:48) [17]

ну и ладно, проктологически дык проктологически :)
"Что поделаешь, привычка." (С) День независимости

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

Мда... ну накрутили... А кто нибудь смотрел код, который генерится при использовании оператора in? Похоже, что нет. :o) А ведь оно работает эффективнее всех ваших шаманств...

← →
Anatoly Podgoretsky (2003-07-17 17:57) [19]

Да еще и к тому не нужно, мощность множества 256

← →
Serginio (2003-07-17 18:05) [20]

Нам не нужно легких путей
idx:=@ByteSet;

For j:=0 To 7 Do
Begin
For i:=0 t0 31 Do

If (1 shl i) and IDX^)>0 Then
s:=S+","+IntToStr(J*32+i);

inc(idx)
End

← →
Skier (2003-07-17 18:09) [21]

Эх, вы, вот как надо ! :))

var
ByteSet: set of byte = [3, 8, 12];
Begin
if ByteSet = [3, 8, 12] then Result := "3,8,12";
End;

← →
vuk (2003-07-17 18:16) [22]

Кстати.

>если бы инспектор объектов так поступал, "тормоза" были бы,
>думаю, ощутимые в некоторых случаях

function TSetProperty.GetValue: string; var S: TIntegerSet; TypeInfo: PTypeInfo; I: Integer; begin Integer(S) := GetOrdValue; TypeInfo := GetTypeData(GetPropType)^.CompType^; Result := "["; for I := 0 to SizeOf(Integer) * 8 - 1 do if I in S then begin if Length(Result) <> 1 then Result := Result + ","; Result := Result + GetEnumName(TypeInfo, I); end; Result := Result + "]"; end;

← →
Альф (2003-07-17 18:19) [23]

2Skier © (17.07.03 18:09)
Суперрр !!!! :)

Большое спасибо всем кто откликнулся :)

← →
Palladin (2003-07-17 18:21) [24]

> Альф © (17.07.03 18:19)

Ну а ты думал :)
Skier, он же Мастер! :)

← →
Skier (2003-07-17 18:22) [25]

>vuk © (17.07.03 18:16)
Вообще на RTTI и Испектор не стоит в этом смысле ориентироваться.
RTTI генерит медленный код, об этом даже в книжках пишут...

← →
vuk (2003-07-17 18:24) [26]

to Skier:
Повторяю ышшо раз. Код с использованием оператора in эффективнее всех этих шаманств. Я скорость мерял.

← →
Skier (2003-07-17 18:27) [27]

>vuk © (17.07.03 18:24)
" Умолкаю, не то по шее получу и подвиг свой не совершу..." :)

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

2 vuk © (17.07.03 18:24)
Нет надо поставить правильный эксперимент со всеми вышеприведенными алгоритмами и выявить процентные расхождения, в том числе и с Net. Причем циклы должны быть как минимум 100 миллиардными. Причем на разных платформах в том числе и 64.

← →
s.ts (2003-07-17 19:25) [29]

По поводу "больше никак", как вам такое ;)
type TS = 1..30; TSOB = set of TS; {$M+} T = class private FSOB: TSOB; published property SOB : TSOB read FSOB; end; {$M-} procedure TForm1.Button1Click(Sender: TObject); var TT : T; begin TT := T.Create; TT.FSOB := [1,2,3]; MessageDlg( GetSetProp(TT,"SOB",true), mtWarning, [mbOK], 0); TT.Free; end;

← →
vuk (2003-07-17 19:44) [30]

to Serginio:
:o) Угу, точно. Займитесь. Я уже все равно померял из любопытства. Просто хотелось прояснить имеет ли смысл весь этот спор. Оказалось, что нет.

Тестировался следующий код.

type TByteSet = Set of Byte; function TForm1.ByteSetToStr(const Value: TByteSet): string; var tmp: string; i : integer; begin tmp := #39; for i := 0 to 255 do if i in Value then begin if Length(tmp) > 1 then tmp := tmp + ","; tmp := tmp + intToStr(i); end; Result := tmp + #39; end; function TForm1.ByteSetToStr2(const Value: TByteSet): string; var i: Integer; idx: Integer; mask: Byte; s: string; begin s := #39; for i := 0 to 255 do begin mask := 1 shl (i mod 8); idx := i div 8; if Boolean(PByteArray(@Value)[idx] and mask) then begin if Length(s) > 1 then s := s + ","; s := s + IntToStr(i); end; end; Result := s + #39; end; procedure TForm1.Button2Click(Sender: TObject); var t1, t2: longint; i, k: integer; b: TByteSet; begin b := [1..255]; for k := 1 to 10 do begin t1 := GetTickCount; for i := 0 to 100000 do ByteSetToStr(b); t2 := GetTickCount; Memo1.Lines.Add( IntToStr(t2-t1)); end; end;

Сделано 10 циклов по 100000 проходов
Замеры проводились при помощи GetTickCount;

Среднее время выполнения одного цикла

на множестве [1..255]:
ByteSetToStr: 32492,2
ByteSetToStr2: 32796,9

на пустом множестве:
ByteSetToStr: 239
ByteSetToStr2: 362,5

Отсюда вывод - шаманить было абсолютно незачем. Мало того, код с использованием in короче и намного более понятен.

← →
vuk (2003-07-17 19:47) [31]

Виноват, получилось не по 100000 а по 100001 проходу. :o) Но сути дела это не меняет.

← →
Serginio (2003-07-17 19:52) [32]

2 vuk © (17.07.03 19:44) Еще бы проверить
Еще бы и Serginio (17.07.03 18:05)
Это я просто пошутил и всегда без особого гемороя применяю IN.
А с другой стороны почему бы и не поизголяться???

← →
vuk (2003-07-17 19:55) [33]

А тот код сначала не компилируется, там лишняя скобка. А после её удаления выдает RangeCheckError. :o)

← →
Radionov Alexey (2003-07-18 10:51) [34]

ответ Чемберлену :)
В три с половиной раза быстрее пред. вариантов, хотя и "нечестное" ускорение.
Function BytesSetToStr3(Const BytesSet: TBytesSet): String; 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 QuartToStr(Q, Offset: Integer): String; Begin Case Q Of 0: Result := ""; 1: Result := ValuesTable[Offset] + ","; 2: Result := ValuesTable[Offset + 1] + ","; 3: Result := ValuesTable[Offset] + "," + ValuesTable[Offset + 1] + ","; 4: Result := ValuesTable[Offset + 2] + ","; 5: Result := ValuesTable[Offset] + "," + ValuesTable[Offset + 2] + ","; 6: Result := ValuesTable[Offset + 1] + "," + ValuesTable[Offset + 2] + ","; 7: Result := ValuesTable[Offset] + "," + ValuesTable[Offset + 1] + "," + ValuesTable[Offset + 2] + ","; 8: Result := ValuesTable[Offset + 3] + ","; 9: Result := ValuesTable[Offset + 0] + "," + ValuesTable[Offset + 3] + ","; 10: Result := ValuesTable[Offset + 1] + "," + ValuesTable[Offset + 3] + ","; 11: Result := ValuesTable[Offset] + "," + ValuesTable[Offset + 1] + "," + ValuesTable[Offset + 3] + ","; 12: Result := ValuesTable[Offset + 2] + "," + ValuesTable[Offset + 3] + ","; 13: Result := ValuesTable[Offset] + "," + ValuesTable[Offset + 2] + "," + ValuesTable[Offset + 3] + ","; 14: Result := ValuesTable[Offset + 1] + "," + ValuesTable[Offset + 2] + "," + ValuesTable[Offset + 3] + ","; 15: Result := ValuesTable[Offset] + "," + ValuesTable[Offset + 1] + "," + ValuesTable[Offset + 2] + "," + ValuesTable[Offset + 3] + ","; End; End; Var k, len: Integer; Bytes: TByteArray Absolute BytesSet; Begin Result := ""; For k := 0 To 31 Do Result := Result + QuartToStr(Bytes[k] And $F, k * 8) + QuartToStr(Bytes[k] Shr 4, k * 8 + 4); len := Length(Result); if Len>0 then SetLength(Result,Len-1); End;

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

> vuk

вот ты завелся-то !) с пол-оборота))

да не претендовал я вовсе на оптимальность, приводя свой вариант) ...
привел его только а-ля "наш ответ Чемберлену"))

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

← →
Serginio (2003-07-18 12:00) [36]

Все таки не смог отказать себе в удовольствии пошаманить и узнал много интересного для себя нужно почаще смотреть в окошко CPU при циклах.

procedure TForm1.Button1Click(Sender: TObject);
Var S:Set of byte;
PC:PCardinal;
i,J,Counter,d,Tic:Integer;
md,tt:Cardinal;
begin

Counter:=0;
// FillChar(s,SizeOf(s),255);
s:=[1,12,78,127,255];
// s:=[];
counter:=0;
Tic:=GetTickCount;
For d:=1 to 10000000 Do
Begin
counter:=0;
For i:=0 to 255 Do
If i in s Then
inc(Counter,i);
end;

Tic:=GetTickCount-Tic;
Memo1.Lines.Add("Set Time="+IntToStr(Tic));
Memo1.Lines.Add(IntToStr(Counter));

Tic:=GetTickCount;
For d:=1 to 10000000 Do
Begin
counter:=0;
PC:=@s;

tt:=0;
For j:=0 to 7 Do Begin
md:=1;
For i:=0 to 31 Do
Begin
// md:=1 shl i;
// If (md and vv)<>0 Then
If (md and PC^)<>0 Then
// If (Cardinal(1 shl i) and PC^)<>0 Then
// Inc(Counter,(j shl 5) + i);
inc(Counter,tt);
md:=md shl 1;
inc(tt);
end;
inc(PC);

end;
end;

Tic:=GetTickCount-Tic;
Memo1.Lines.Add("Cardinal Time="+IntToStr(Tic));
Memo1.Lines.Add(IntToStr(Counter));
end;

Вот результаты
Пустой Set
Set Time=7984
0
Cardinal Time=5859
0

Не пустой Set
Set Time=8344
473
Cardinal Time=6203
473

Специально оставил заремленный код крайне не эффективный и тормозящий. Хотя вызовов Inc(Counter,(j shl 5) + i);
было например 1/246 тормозил на секунду.
Надо вспоминать ассемблерные инструкции и сопоставлять с компиляцией Delphi.
Надо провести тест на Net и обязательно в 1С думаю добьюсь там более впечатляющих результатов (Только жалко, что в 1С нет окошечка CPU)

← →
Digitman (2003-07-18 12:53) [37]

var MySet: set of byte = [3, 8, 12]; procedure BitSetToStr(BitSet: PByteArray; Str: PChar); const divider: byte = 10; asm push ebx push esi push edi mov edi, eax mov byte ptr [edx], 39 inc edx sub esi, esi mov ecx, esi @@1: bt [edi], ecx jnc @@4 test esi, esi je @@2 mov byte ptr [edx], "," inc edx @@2: inc esi mov eax, ecx div divider mov bl, ah sub ah, ah div divider mov bh, ah sub ah, ah div divider and ah, ah je @@_10 add ah, "0" mov byte ptr [edx], ah inc edx @@_10: and bh, bh je @@_1 add bh, "0" mov byte ptr [edx], bh inc edx @@_1: and bl, bl je @@4 add bl, "0" mov byte ptr [edx], bl inc edx @@4: inc ecx cmp ecx, 256 jb @@1 mov byte ptr [edx], 39 pop edi pop esi pop ebx end; procedure TfrmMain.Button1Click(Sender: TObject); var s: string; begin s := StringOfChar(" ", 1026); //****************************** BitSetToStr(@MySet, PChar(s)); //****************************** showmessage((trim(s))); end;

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

Не так не интересно. Нужно создавая обычный дельфевый код добиваться его эффективной компиляции.

← →
Radionov Alexey (2003-07-18 13:52) [39]

>Digitman © (18.07.03 12:53)
"Ответ Чемберлену" вышел какой-то слишком резкий :))
Работает шустро. Мой код медленнее больше, чем в полтора раза на малых мн-вах. А на [0..255] аж в 14 раз :)

Что ж. Будем пробовать отвечать тем же и с трезвой головой (если забава покажется стоящей того) :)

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

> Radionov Alexey

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

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

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

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