liczby i bity w c++/builder

[Gość]

mam tablice :tablica[x] typu integer kazda liczba w tej tablicy zajmuje 32 bity co jest bardzo wielkim obszarem przy np 10 milionach liczb. Wiem ze mozna by bylo przedstawiac liczby w/na bajtach(1bajt=8bitow) co dramatycznie zmniejszyloby zuzycie pamieci w moim programie. pytanie jak to zrobic w c++ ? czy chodzi tu o zapisywanie liczb binarnie ? nie chcialbym raczej jakiegos gotowego programu lecz łopatologiczne wytlómaczenie problemu?

[yasin]

po co Ci taka tablica (?) imho to jest chyba nieistotne jak bedziesz zapisywal te liczby, proponuje dynamicznie allokowac, dokladnie tyle ile potrzeba

[Gość]

tablica jest dynamicznie alokowana!!!! jest w niej dokladnie tyle pozycji ile ma byc chodzi o to dokladnie ze 10mln liczb integer 32 bitowych zajmuje 10mln*32bit/8bit/1024/1024=ok 38 megabajtow pamieci a 20mln a 30 mln itd dla tego o to pytam jak kots wie to prosze o odpowiedz

[JEdi]

Jesli to sa male liczby to zapisuj je jako char'y. Char zajmuje 1 bajt i po problemie.

[Gość]

no tak chary na poczatku wystarcza ale dla liczb 16 cyfrowych? i wiekszych?

[Gość]

musze dodatkowo móc wykonywać operacje dodawania lub dzielenia na tych liczbach

[JEdi]

Dodawanie i dzielenie na charach to nie taki problem, konwersja i po problemie. A na 1 bajcie nie zapiszesz wiekszej liczby niz 255, na 2 65355 itp... Zreszta liczby przeciez sa zapisywane w takiej tablicy binarnie... wiec nie wiem o co chodzi ;D

[Gość]

czyli mosialbym napisac makrodefinicje dla charow wiekszych niz 255?

[Gość]

dokładnie chodzi mi o cos takiego jak to napisac w c++ " zastosowanie bitów do reprezentacji kolejnych liczb - 1 bajt zawiera 8 bitów, więc w jednej komórce pamięci można zmieścić informację o 8 liczbach naturalnych. Tablica zajmująca 1MB zawiera ich ponad 8 milionów."

[JEdi]

Hmm ... jedyny co mi przychodzi na mysl, ze 1 liczba w tej tablicy to jakas tam sobie liczba, a pozniej w zaleznosci od bitu jest liczba wieksza o 1 , badz mniejsza o 1. Jesli tak to ma wygladac to powiedz to powiem jak moze wygladac reszta (tak mi sie wydaje, ze wiem ;D).

[Gość]

dokladnie o 1 wieksza beda to przedzialy liczb od 1 do n to jest cel podstawowy drugi cel to zeby petla for wpisywala do tablicy liczby od 1 do n ale nieparzyste(wiem jak to zrobic) wiec jak bys mogł to prosze o wyjasnienie

[JEdi]

Znowu zglupialem, nie wiem po prostu do czego dazysz.

[Wojt]

dokładnie chodzi mi o cos takiego jak to napisac w c++ " zastosowanie bitów do reprezentacji kolejnych liczb - 1 bajt zawiera 8 bitów, więc w jednej komórce pamięci można zmieścić informację o 8 liczbach naturalnych. Tablica zajmująca 1MB zawiera ich ponad 8 milionów."

Zgaduj-zgadula: chcesz mieć tablicę z adresowalnymi bitami ??

[Gość]

uff moze wyjasnie to tak teraz mam tablice dynamicznie przydzielana z liczbami integer dla zakresow od 1 do n typ integer zajmuje 32 bity a uzywam duzych zakresow liczb wiec moj prog pozera ogromne ilosci pamieci pomyslalem ze mozna by to zrobic na charach albo bitach zeby zaoszczedzic pamiec? i co wy na to? to raczej nie jest trudne do zrobienia? pls. help

[Gość]

no tak chary na poczatku wystarcza ale dla liczb 16 cyfrowych? i wiekszych?

Sam sobie odpowiedziales... Jesli liczby maja byc dowolnej wielkosci to zapomnij o char. Malo tego... skoro tu piszesz o liczbach 16 cyfrowych to nawet int do takich nie wystarczy.

Chyba, ze caly zbior duzych liczb bedzie sie zawieral w dosc skumulowanym przedziale, np. 90000000-100000000. Wtedy dla duzej ilosci liczb w tym przedziale (prawie pelny, czyli niecale 10mln liczb) mozna to efektywniej zapisac bitowo (zamiast ponad 30MB dla int'ow mozna by sie zmiescic w ok 1MB).

 

Sprecyzuj moze do czego Ci to potrzebne, jak duze liczby chcesz przechowywac, bo jak narazie to nie do konca czuje do czego dazysz.

[Gość]

uff nareszcie ktos mnie zrozumiał(FiDO) to ze chary nie wystarcza to wiem zostaja raczej bajty jezeli chodzi o 16 cyfrowe to builder takie obsluguje(__in64 itd. ale nie w tym rzecz) Konkretnie w czym bym chcial pomocy

1. Jak zadeklarowac(dynamicznie) tablice operujaca na bajtach (to jest relatywnie proste) w tablicy bede przechowywal liczby zawsze od 1 do n

2. musze miec mozliwosc wpisania liczb do tablicy i ich dzielenia lub dodawania

3. wypis liczb z tablicy

Mam takie cos zrobione jak juz pisalem i chodzi mi o optymalizacje tego ze wzgledu na ogromna pamieciozernosc tak naprawde to pracuje nie na 32 bitach ale na 64 bitach co jest jeszcze wieksza masakra

[Gość]

Wtedy dla duzej ilosci liczb w tym przedziale (prawie pelny, czyli niecale 10mln liczb) mozna to efektywniej zapisac bitowo (zamiast ponad 30MB dla int'ow mozna by sie zmiescic w ok 1MB).

dokladnie tak jak napisales tylko jak to zrobic w c++/builder

[Gość]

1. Jak zadeklarowac(dynamicznie) tablice operujaca na bajtach (to jest relatywnie proste) w tablicy bede przechowywal liczby zawsze od 1 do n

Jak duze moze byc n ?? Jak geste moze byc zapelnienie tej tablicy ?

Jesli chcesz np. przechowywac liczby od 1 do jakiejs duzej liczby (skoro mowisz o kilkunastocyfrowych) to zapis bitowy moze sie nie oplacic, wiec podaj zalozenia.

aha... ja jeszcze przy tym zapisie bitowym zalozylem (bo akurat takie zalozenie mialem w tym co kiedys robilem), ze dana liczba w tablicy moze wystepowac tylko raz, jesli ma byc inaczej to zapis bitowy coraz bardziej przestaje sie oplacac, ale to nadal zalezy od sredniego wypelnienia tablicy.

 

Najlepiej wiec podaj cos wiecej o tym, do czego Ci to potrzebne (chyba nie jakis tajny projekt ? ;) ), jakas specyfike tych liczb itp. itd.

[Gość]

oczy wiscie np juz podaje tylko nie rozumie co to znaczy "Jak geste moze byc zapelnienie tej tablicy " tablica zapelniona zawsze bedzie w 100%(bo jest dynamiczna) liczby w tablicy beda przedzialami od x do y co 1 czyli np tablica 10 elementowa od 1 do 10 1,2,3,4,5,6,7,8,9,10. liczby standardowo minimalna wielkosc tablicy to 10mln(wiem ze to sie kloci z dynamiczna tablica ale na razie zalozmy ze bedzie statyczna zawsze 10 mln elemntow) liczb (czy od 1 do 10mln czy od 20mln do 30mln to nie ma dla mnie znaczenia) Oczywiscie dana liczba bedzie wystepowac w tablicy tylko raz co jest oczywiste dla przedzialow ktore podalem.

Co do specyfikacji liczb to sa ta liczby całkowite, dajmy na poczatek zakres unsigned long integer to maxylna wartosc liczby (na poczatek zapominamy o 16 cyfrowych), liczby sa liczbami kolejnymi czyli zawsze x++, (np:1,2,3,4,5,6, czy tez 10,11,12,13, itd).

tak jak napisalem wyzej potrzebuje wiedzec jak w c++/builder zadeklarowac ta tablice jak z niej korzystac i wypisywac (na ekran).

-----

Co do twojego pytania o TAJNY PROJEKT :)) to bedzie to benCZmark :) a co innego milabym niby pisac jako uczestnik tweak.pl :)))

-----

Oczywiscie jak go skoncze to kazdy zainteresowany bedzie mogł go potestowac....lecz na razie program wymaga optymalicazji....bedzie to benCZmark matematyczny wzoruje sie na wielu zagramanicznych benczach....jednym z testow bedzie algorytm na poszukiwanie liczb pierwszych (oparty na sicie eratostenes'a ktore bardzo zmodyfikowalem)...

.....

Za kilka godzin wyjezdzam i dostep do netu odzyskam dopiero w piatek, wiec bardzo bym liczyl na pomoc, nie chodzi mi o pospiech tylko wogule o pomoc bo do piatku i tak nie skoncze tego programu...

[Gość]

oczy wiscie np juz podaje tylko nie rozumie co to znaczy "Jak geste moze byc zapelnienie tej tablicy "

Zle napisalem, chodzilo mi o gestosc zapelnienia tego zadanego przedzialu liczbami... np. jak mamy przedzial 1 do 10.000.000 to przy gestosci ok 90% mamy ok 9.000.000 liczb w nim. Chcialem to wiedziec po to, zeby stwierdzic oplacalnosc przejscia na zapis bitowy. Dobrze by bylo, gdyby te przedzialy nie byly zbyt duze, bo to ich rozmiar ma decydujace znacznie o tym, ile tablica z tymi liczbami zajmie, np. przy "szerokosci" przedzialu 10.000.000 tablica taka zajmie troszke ponad 1MB, dla 100.000.000 juz ponad 10MB (gdyby to samo zapisac tradycyjnie zajmowaloby ok 380MB :D [przy zalozeniu prawie calkowitego wypelnienia przedzialu liczbami])

 

Co do specyfikacji liczb to sa ta liczby całkowite, dajmy na poczatek zakres unsigned long integer to maxylna wartosc liczby (na poczatek zapominamy o 16 cyfrowych), liczby sa liczbami kolejnymi czyli zawsze x++, (np:1,2,3,4,5,6, czy tez 10,11,12,13, itd).

tak jak napisalem wyzej potrzebuje wiedzec jak w c++/builder zadeklarowac ta tablice jak z niej korzystac i wypisywac (na ekran).

Wiec tak.. wyjasnie Ci idee takiego zapisu tablicy liczb.

Po pierwsze tablica taka bedzie wbrew pozorom statyczna (ale za to nie bedzie sie zwiekszac jak przybywac beda liczby), jej wielkosc w bajtach to:

ilosc_liczb_w_przedziale / 8 zaokraglone w gore.

Na poczatek dla przyklady zalozmy ze chcemy zapisac liczby z przedzialu 1-20, czyli w sumie 20 mozliwych liczb w tablicy:

20 / 8 = 2.5 => 3

czyli

char tab[3];

Standardowo zerujemy tablice.

Jak chcesz zapisac do niej pierwsza liczbe z przedzialu, czyli 1 to pierwszy bit ustawiamy na 1, czyli bedzie ona wygladac tak:

10000000 00000000 00000000

 

Po dodaniu 5 i 10:

 

10001000 01000000 00000000

 

Czyli po prostu bit jest ustawiony na tym indeksie, ktora liczbe trzymamy.

Jak widac dodawanie kolejnych liczb nie powoduje zwiekszenia tablicy.

Zeby trzymac np. liczby z przedzialu 10mln-20mln trzeba jeszcze zapisac index poczatkowy (10mln - 1 => 9.999.999) i dalej tak samo, czyli jak chcemy zapisac liczbe 10mln to odejmujemy najpierw od niej index poczatkowy: 10mln - (10mln - 1) = 1 i to jest indeks na ktorym trzeba ustawic bit. Podobnie w druga strone przy odczycie takich liczb.

Zapis/odczyt do/z takiej tablicy to fajna zabawa z przesunieciami bitowymi,maskami itp ;) Radze wiec, skoro korzystasz z C++, napisac sobie do czegos takiego klase z jakims wygodnym API, zeby mozna by latwo operowac na niej.

Nie wiem tylko czy akurat taka reprezentacja bedzie Tobie odpowiadac, bo nie wiem co chcesz z tymi liczbami robic.. jak jakies skomplikowane operacje to moze sie to okazac niewydajne.

Co do twojego pytania o TAJNY PROJEKT :)) to bedzie to benCZmark :) a co innego milabym niby pisac jako uczestnik tweak.pl :)))

No to czekamy :) Tylko nie powiel błędów CCR'a ;)