Megaset

[apl]

Witam, w tym poście chcę przedstawić moje rozwiązanie dotyczące tworzenia i posługiwania się zbiorami o dowolnej wielkości. Krytyka i alternatywne propozycje mile widziane.
Biblioteka i kody źródłowe do pobrania ze strony https://apl.home.amu.edu.pl/apl/
Pozdrawiam,
apl

Typ zbiorowy w Delhi pozwala operować na zbiorach zawierających do 256 elementów. Stan ten można łatwo zmienić. Przedstawiamy tu metodę tworzenia i obsługi zbiorów o praktycznie nieograniczonej licz-bie elementów.
W Delhi (jak również i w Turbo-Pascalu), wartości typu zbiorowego są odnotowywane w ten sposób, że każdemu elementowi zbioru jest przyporządkowany jeden bit. Ustawienie bitu na 1 sygnalizuje obecność elementu, a ustawienie na 0 jego nieobecność. Każdy bajt może zatem kodować obecność ośmiu elemen-tów. Ten sposób kodowania zbiorów jest bardzo oszczędny i z tego względu chcieliśmy go zachować.
Delhi przeznacza na zapis zmiennej zbiorowej nie więcej niż 32 bajty, stąd wspomniane ograniczenie li-czebności zbiorów. Można to zmienić przeznaczając na kodowanie zbiorów strukturę o większych roz-miarach, np. tablica array[byte] of byte pozwoli zapisywać zbiory o 2048 elementach. Wystarczy więc zadeklarować tablicę o odpowiednio dużych rozmiarach o elementach typu byte (ze względu na prostotę obliczeń) i następnie utworzyć podprogramy modyfikujące i odczytujące odpowiednie bity owej struktury, aby móc posługiwać się zbiorami o nieograniczonej praktycznie wielkości.
Do właściwego bitu można dotrzeć posługując się maskami i operacjami bitowymi. Zakładając że ele-menty tablicy są indeksowane zaczynając od 0, bajt w którym znajduje się bit związany z danym elemen-tem zbioru można obliczyć wg wzoru
m= i div 8,
a numer bitu wg wzoru
n=i mod 8,
gdzie i jest numerem elementu, zaś maska, to liczba
l=1 shl n.

Przykładowo, przy deklaracjach

type TarrSet = array[byte] of byte;
procedure ilmn(const i:word;var l,m,n:word);

Begin
m:=i div 8;
n:=i mod 8;
l:=1 shl n;
End;{lmn}

elementy do zbioru można włączać za pomocą procedury:

procedure includeToSet(var s:TarrSet;i:word);
//włącza liczbę i do zbioru s
var l,m,n:word;
Begin
ilmn(i,l,m,n);
s[m]:=l or s[m];
End;{includeToSet}

W załączonym tekście modułu pn. „Megasety” zamieszczamy podprogramy do włączania i wyłączania elementów ze zbioru, obliczania sumy różnicy i iloczynu zbiorów, sprawdzania zawartości zbioru i przy-należności elementu do zbioru. Dołączamy też prosty program demonstrujący ich użycie.

Andrzej Pluciński
a...@amu.edu.pl

[J-23]

W dniu 2022.01.10 o 14:34, apl pisze:

1. Piszesz w środowisku IDE Delphi a nie Delhi - o ile pierwszy raz
myślałem że to literówka - tak za n-tym razem zrozumiałem że to
literówką nie jest.

2. Opisałeś dość dobrze co przedstawiasz lecz problem jest w tym że nie
sprecyzowałeś czego szukasz - działania na zbiorach można wykonać na
wiele sposobów - Jeśli pytasz czy twoje rozwiązanie jest dobre to ja Ci
odpowiem zależy do czego chcesz go użyć

Pozdrawiam
J-23

[apl]

> 1. Piszesz w środowisku IDE Delphi a nie Delhi - o ile pierwszy raz
> myślałem że to literówka - tak za n-tym razem zrozumiałem że to
> literówką nie jest.
>
> 2. Opisałeś dość dobrze co przedstawiasz lecz problem jest w tym że nie
> sprecyzowałeś czego szukasz - działania na zbiorach można wykonać na
> wiele sposobów - Jeśli pytasz czy twoje rozwiązanie jest dobre to ja Ci
> odpowiem zależy do czego chcesz go użyć
>
> Pozdrawiam
> J-23

Dzięki za uznanie. "Delhi", to efekt autokorekty w Wordzie, no ale powinienem był to dostrzec. No cóż, potrzeba matką wynalazków. Prezentowany wynalazek był podyktowany koniecznością podyktowaną przez program analizy skupień w zagadnieniu kwantyzacji wektorowej i to nawet nie ogromnym zbiorem danych (tu zastosowałem podejście oparte na skorowidzach (to inny mój wynalazek)), ale rozmiarami klasyfikowanych wektorów.
Pozdrawiam,
a...@amu.edu.pl

[Roman Tyczka]

On 10.01.2022 14:34, apl wrote:
> Witam, w tym poście chcę przedstawić moje rozwiązanie dotyczące tworzenia i posługiwania się zbiorami o dowolnej wielkości. Krytyka i alternatywne propozycje mile widziane.
> Biblioteka i kody źródłowe do pobrania ze strony https://apl.home.amu.edu.pl/apl/
> Pozdrawiam,
> apl

A potem wchodzi cały na biało ISet<T> ze Springa:

https://spring4d.4delphi.com/docs/develop/Html/index.htm?Spring.Collections.ISet.htm

i pozamiatał...

--
pzdr
Roman

[Adam Siwoń]

W dniu 2022-01-10 o 14:34, apl pisze:

> Witam, w tym poście chcę przedstawić moje rozwiązanie dotyczące tworzenia i posługiwania się zbiorami o dowolnej wielkości. Krytyka i alternatywne propozycje mile widziane.
> Biblioteka i kody źródłowe do pobrania ze strony https://apl.home.amu.edu.pl/apl/

[...]

Wtrącę swoje 3 grosze. Nie wchodząc w samą funkcjonalność biblioteki
masz trochę rzeczy do posprzątania:
1. Wpięcie kodu obsługującego warstwę wizualną w obliczeniach:

procedure includeToMegaSet(var s:TarrSet;i:longword);

//włącza liczbę i do zbioru

var l,m,n:longword;
Begin
ilmn(i,l,m,n); //number, mask, member, bit
if m<=high(s) then s[m]:=l or s[m]
else showMessage('Procedure "IncludeToMegaSet", program
error.'#13#10'Number '+intToStr(m)+
' could not be included to set because was too big (because of lack
of the target container capacity).'#13#10+
'Numbers should be<='+intToStr(high(s)));
End;{includeToMegaSet}
Mam na myśli te nieszczęsne ShowMessage. Jeśli użyjesz tej biblioteki w
jakimś kodzie działającym w usłudze sieciowej, to będziesz zaglądał na
konsolę serwera co tam się wyświetla? Nie. Więc nie wywołuj komunikatów
dla użytkownika w kodzie wykonującym obliczenia, zarządzającym
strukturami itp. Od tego jest warstwa wizualna. Użyj wyjątków jeśli
musisz zgłosić błąd krytyczny.

2. Jeśli piszesz w nowszych Delphi, a tak to wygląda, to rozważ użycie
rekordów do opakowania typu. Dla rekordu możesz przeciążać operatory,
więc użycie Twojego typu zbiorowego nie wymagało by dedykowanych
funkcji, ale dało by się tego używać jak standardowy typ zbiorowy w
Pascalu (operatory Include, Exclude, in, dodawania, przypisania...)
Pomyśl jak łatwa była by wtedy migracja kodu programu ze standardowego
typu na Twój. Wystarczyła by korekta deklaracji?

3. Z samych testów - biblioteka odwołuje się do unitu z testami - tak
być nie powinno, bo program, który używa biblioteki musi też używać
unitu testów.
Zamiast tworzyć jakieś własne rozwiązania okienkowe do testowania czemu
nie użyjesz standardowej biblioteki do obsługi testów jednostkowych?
(np. DUnit, DUnitX)

Powodzenia.

--
z pozdrowieniami
Adam Siwoń

[a...@amu.edu.pl]

Dzięki, kolego za inspirujące uwagi. Każdy z nas ma na uwadze różne zastosowania. Ważne jest wdrożenie pewnej idei. Załączony kod może być pomocny w indywidualnych rozszerzeniach, czy implementacjach (byłbym wdzięczny za podzielenie się takimi rozwiązaniami).
Funkcjonalnie moje rozwiązanie różni się od standardowego jedynie tym, że uzewnętrzniony jest jeden "flak" - kontener na pomieszczenie w nim pewnego zbioru liczbowego. To pozwala na dowolne określanie - stosownie do aktualnych potrzeb - jego rozmiaru poprzez alokację odpowiedniej ilości RAM-u (najlepiej dynamicznie). W rozwiązaniu standardowym kontener ten jest ukryty i stały, 32 bajtowy, co - jak pisałem w uzasadnieniu - ogranicza maksymalny rozmiar kodowanych zbiorów do 32 elementów. Tak więc "Megasety" funkcjonują inaczej - w procedurach konieczne jest jawne odwoływanie się do owego kontenera. Konieczne jest więc wyraźne rozróżnienie identyfikatorów ppr. do ich obróbki, aby uniknąć zamieszania.
Pozdrawiam,
apl