Någon som har lite tid över och är en hejare på att skriva snabb kod i C och kan VB hjälpligt?

Jag har skrivit ett program i VB6 där vissa uträkningar tar lite för lång tid så jag funderade på att göra det i C. Men det var ett tag sen jag höll på med C så jag vill veta om det snabbar upp programmet ordentligt?

Jag har skrivit en betydligt längre kod (det är därför den kan se lite konstig ut) men det är denna kod som körs mest så det är den som avgör hur snabb koden är.
Så om någon vänlig person kan skriva ett program i C som gör samma saker (men behöver inte vara på liknande sätt) och mäta hur stor procentskillnad det är mot detta program i VB.

intTmpRader vet jag inte hur man ska simulera på bästa sätt men den kommer inte att innehålla så många poster igentligen (max ca 500) och kommer att tömmas då och då(nästlade loopar) så om ni vill göra på att sätt gör likadant i VB som i C.

ps jag började använda int men bytte till long och jag har inte hunnit ändra namnen än.


<code>
Option Explicit
Private Const BitMask_0 = &H1
Private Const BitMask_1 = &H2
Private Const BitMask_2 = &H4
Private Const BitMask_3 = &H8
Private Const BitMask_4 = &H10
Private Const BitMask_5 = &H20
Private Const BitMask_6 = &H40
Private Const BitMask_7 = &H80
Private Const BitMask_8 = &H100
Private Const BitMask_9 = &H200
Private Const BitMask_10 = &H400
Private Const BitMask_11 = &H800
Private Const BitMask_12 = &H1000

Private Sub Command1_Click()
Dim intAntalRattTecken&, intAntalRattRader&
Dim intTmpRader(100000)& 'beror på hur stor loop som används
Dim intTemptal&, intTemptal2&, XOR_Tal&
intTemptal = 8000
intTemptal2 = 1456

For y = 0 To ??????? 'beror på processor

XOR_Tal = intTempTal Xor intTempTal2

'Räknar ut hur många ettor det är i det binära talet. Största talet den ska
'klara är 8191
intAntalRattTecken = Abs(((XOR_Tal And BitMask_0) > 0) + ((XOR_Tal And BitMask_1) > 0) + ((XOR_Tal And BitMask_2) > 0) + ((XOR_Tal And BitMask_3) > 0) + ((XOR_Tal And BitMask_4) > 0) + ((XOR_Tal And BitMask_5) > 0) + ((XOR_Tal And BitMask_6) > 0) + ((XOR_Tal And BitMask_7) > 0) + ((XOR_Tal And BitMask_8) > 0) + ((XOR_Tal And BitMask_9) > 0) + ((XOR_Tal And BitMask_10) > 0) + ((XOR_Tal And BitMask_11) > 0) + ((XOR_Tal And BitMask_12) > 0)


If (y mod 10) = 0 Then
intAntalRattRader = intAntalRattRader + 1
intTmpRader(intAntalRattRader) = y
End If
Next y

End Sub

</code>

Hej Herman,

att räkna ut hur många bitar som är satta i ett tal varje gång är onödigt, antalet ändras ju aldrig. Det man gör istället för att räkna ut dem varje gång är att skapa en array med alla tal i (eller en delmängd av dem). Exempel i C:

<code>
char bit_count[] = {
0, /* 0 */ 1, /* 1 */ 1, /* 2 */ 2, /* 3 */ 1, /* 4 */
2, /* 5 */ 2, /* 6 */ 3, /* 7 */ 1, /* 8 */ 2, /* 9 */
2, /* 10 */ 3, /* 11 */ 2, /* 12 */ 3, /* 13 */ 3, /* 14 */
4, /* 15 */ 1, /* 16 */ 2, /* 17 */ 2, /* 18 */ 3, /* 19 */
2, /* 20 */ 3, /* 21 */ 3, /* 22 */ 4, /* 23 */ 2, /* 24 */
3, /* 25 */ 3, /* 26 */ 4, /* 27 */ 3, /* 28 */ 4, /* 29 */
4, /* 30 */ 5, /* 31 */ 1, /* 32 */ 2, /* 33 */ 2, /* 34 */
3, /* 35 */ 2, /* 36 */ 3, /* 37 */ 3, /* 38 */ 4, /* 39 */
2, /* 40 */ 3, /* 41 */ 3, /* 42 */ 4, /* 43 */ 3, /* 44 */
4, /* 45 */ 4, /* 46 */ 5, /* 47 */ 2, /* 48 */ 3, /* 49 */
3, /* 50 */ 4, /* 51 */ 3, /* 52 */ 4, /* 53 */ 4, /* 54 */
5, /* 55 */ 3, /* 56 */ 4, /* 57 */ 4, /* 58 */ 5, /* 59 */
4, /* 60 */ 5, /* 61 */ 5, /* 62 */ 6, /* 63 */ 1, /* 64 */
2, /* 65 */ 2, /* 66 */ 3, /* 67 */ 2, /* 68 */ 3, /* 69 */
3, /* 70 */ 4, /* 71 */ 2, /* 72 */ 3, /* 73 */ 3, /* 74 */
4, /* 75 */ 3, /* 76 */ 4, /* 77 */ 4, /* 78 */ 5, /* 79 */
2, /* 80 */ 3, /* 81 */ 3, /* 82 */ 4, /* 83 */ 3, /* 84 */
4, /* 85 */ 4, /* 86 */ 5, /* 87 */ 3, /* 88 */ 4, /* 89 */
4, /* 90 */ 5, /* 91 */ 4, /* 92 */ 5, /* 93 */ 5, /* 94 */
6, /* 95 */ 2, /* 96 */ 3, /* 97 */ 3, /* 98 */ 4, /* 99 */
3, /* 100 */ 4, /* 101 */ 4, /* 102 */ 5, /* 103 */ 3, /* 104 */
4, /* 105 */ 4, /* 106 */ 5, /* 107 */ 4, /* 108 */ 5, /* 109 */
5, /* 110 */ 6, /* 111 */ 3, /* 112 */ 4, /* 113 */ 4, /* 114 */
5, /* 115 */ 4, /* 116 */ 5, /* 117 */ 5, /* 118 */ 6, /* 119 */
4, /* 120 */ 5, /* 121 */ 5, /* 122 */ 6, /* 123 */ 5, /* 124 */
6, /* 125 */ 6, /* 126 */ 7, /* 127 */ 1, /* 128 */ 2, /* 129 */
2, /* 130 */ 3, /* 131 */ 2, /* 132 */ 3, /* 133 */ 3, /* 134 */
4, /* 135 */ 2, /* 136 */ 3, /* 137 */ 3, /* 138 */ 4, /* 139 */
3, /* 140 */ 4, /* 141 */ 4, /* 142 */ 5, /* 143 */ 2, /* 144 */
3, /* 145 */ 3, /* 146 */ 4, /* 147 */ 3, /* 148 */ 4, /* 149 */
4, /* 150 */ 5, /* 151 */ 3, /* 152 */ 4, /* 153 */ 4, /* 154 */
5, /* 155 */ 4, /* 156 */ 5, /* 157 */ 5, /* 158 */ 6, /* 159 */
2, /* 160 */ 3, /* 161 */ 3, /* 162 */ 4, /* 163 */ 3, /* 164 */
4, /* 165 */ 4, /* 166 */ 5, /* 167 */ 3, /* 168 */ 4, /* 169 */
4, /* 170 */ 5, /* 171 */ 4, /* 172 */ 5, /* 173 */ 5, /* 174 */
6, /* 175 */ 3, /* 176 */ 4, /* 177 */ 4, /* 178 */ 5, /* 179 */
4, /* 180 */ 5, /* 181 */ 5, /* 182 */ 6, /* 183 */ 4, /* 184 */
5, /* 185 */ 5, /* 186 */ 6, /* 187 */ 5, /* 188 */ 6, /* 189 */
6, /* 190 */ 7, /* 191 */ 2, /* 192 */ 3, /* 193 */ 3, /* 194 */
4, /* 195 */ 3, /* 196 */ 4, /* 197 */ 4, /* 198 */ 5, /* 199 */
3, /* 200 */ 4, /* 201 */ 4, /* 202 */ 5, /* 203 */ 4, /* 204 */
5, /* 205 */ 5, /* 206 */ 6, /* 207 */ 3, /* 208 */ 4, /* 209 */
4, /* 210 */ 5, /* 211 */ 4, /* 212 */ 5, /* 213 */ 5, /* 214 */
6, /* 215 */ 4, /* 216 */ 5, /* 217 */ 5, /* 218 */ 6, /* 219 */
5, /* 220 */ 6, /* 221 */ 6, /* 222 */ 7, /* 223 */ 3, /* 224 */
4, /* 225 */ 4, /* 226 */ 5, /* 227 */ 4, /* 228 */ 5, /* 229 */
5, /* 230 */ 6, /* 231 */ 4, /* 232 */ 5, /* 233 */ 5, /* 234 */
6, /* 235 */ 5, /* 236 */ 6, /* 237 */ 6, /* 238 */ 7, /* 239 */
4, /* 240 */ 5, /* 241 */ 5, /* 242 */ 6, /* 243 */ 5, /* 244 */
6, /* 245 */ 6, /* 246 */ 7, /* 247 */ 5, /* 248 */ 6, /* 249 */
6, /* 250 */ 7, /* 251 */ 6, /* 252 */ 7, /* 253 */ 7, /* 254 */
8 /* 255 */
};

int main(void)
{
unsigned int x = 8191;

printf("Number of bits in %d = %d\n",
x,
/*
bit_count[(x>>24) & 0xff] +
bit_count[(x>>16) & 0xff] +
Ovanstående rader behöver du inte eftersom max(x) var 8191.
*/
bit_count[(x>>8) & 0xff] +
bit_count[x & 0xff]);

return 0;
}

</code>

Jag vet inte hur man skriver det i VB, men det måste gå att göra i det språket också annars är det helt hjärndött. :-)

Du kan öka antalet tal i arrayen om du vill få det att gå ännu snabbare, men då kommer arrayen att ta mer plats.

/Tommy

Jag tror inte man kan använda shifts i VB... Men vill du ha hastighet borde du verkligen lära dig lite ASM! Mycket snabbare att utföra beräkningar på register än minne, dessutom är det inte mycket svårare:
C: var << 16
ASM: SHL eax, 16 (förutsatt att man har laddat var till eax)

Nu gällde ju frågan C och inte assembler. Om snabbheten är det ytterst viktiga så skulle jag lägga hela nummerserien i en array så att det bara var att slå upp resultatet. Om inte DET går att fixa i VB så blir jag lite orolig. Finns inte shift i VB???

Vad menar du med shift?

/ Peter

Att shifta bitar = rotera bitarna i ett tal...

t.ex. 8 kan skrivas som:
1000

Shifta 1000 ett steg åt vänster ger:
10000 (16 decimalt)

...och åt höger ger:
0100 (4 decimalt)

Hej igen.

Jo det kan var intressant om det finns något snabbare sätt att lösa det i VB men det jag helst vill veta är hur mycket snabbare ( i %) man kan få ovan kodsnutt i C.
Har ingen C kompilator i datorn nu. Och har glömt mycket av C så jag vill veta om det är värt att sätta sig in i C igen.

ps. Håller inte på att programmera så mycket nu. Men fick för mig att jag skulle kasta ihop ett stryktips program.

Jag vet inte om det här blir en ekvivalent jämförelse (jag kan inte VB), men följande program tog 0,4 sekunder att exekvera på min gamla 233 MHz burk med 32 MByte minne. Allt programmet gör, i stort sett, är att slå upp data i minnet.

<code>
#define LOOP_MAX 5000000

int main(void)
{
static char result_array[LOOP_MAX];
int i, x;

for (i = 0; i < LOOP_MAX; ++i) {
x = i % 8192;

result_array[i] = bit_count[(x>>8) & 0xff] + bit_count[x & 0xff];
}

return 0;
}
</code>
Hur lång tid tar din VB kod att köra på din maskin och vad är det för maskin du kör på?
<p>
bit_count arrayen finns i mitt första inlägg.

Mitt förslag. Tror inte det kan göras mycket snabbare (f.ö. är int/ unsigned int rätt variabel att använda i C):

unsigned int XOR_Tal=9, antal=0;
for (int pos=0;pos < sizeof(XOR_Tal)*8-1; pos++)
antal+=(XOR_Tal<<(sizeof(XOR_Tal)*8-pos-1))>>sizeof(XOR_Tal)*8-1;


/Niklas Jansson

> shifta bitar = rotera bitarna i ett tal
Det är ju inte helt rätt. Då heter det ju rotation. En shift tar ju bort information om man skiftar ut den.

/Niklas Jansson

Om det skall vara petigt är det också fel, för den utskiftade biten hamnar i Carry-flaggan...

Tommy kan du skicka exe filen hit? Men gör så den tar ca 1-2min på din dator.
För då är det lättare att jämföra med stoppur (kanske finns någon smart metod att räkna på datorn?) Och skicka med den exakta koden också.

Jag testade den på min dator 266mhz 128mb och winME. Men som sagt det är svårt att jämföra mellan olika datorer och hur räknade du ut tiden? Den metoden jag använde i VB kan jag inte säga säkert att den räknar sekunderna rätt? Men enligt den fick jag 1,3sek.


herman@owns.it

>Om det skall vara petigt är det också fel, för den utskiftade biten hamnar i Carry-flaggan...
Nu bör vi väl inte ha denna diskussion här (det var fel av mig från början...) men vid en skift fler steg än ett förlorar du visst information.

Sen är jag lite skeptisk till tommys variant... Varför hålla på med arrayer?
Det skall väl bara tas fram antalet binära ettor?

--

Sedan kan VB-lösningen förbättras genom att du helt enkelt flyttar ut beräkningen av antalet ettor utanför loopen. Det verkar som helt meningslöst att räkna om den vid varje loop. (Men du kanske har klippt bort kod som använder den inuti loopen)

/Niklas Jansson

Hej Niklas, vad menar du när du skriver "f.ö. är int/ unsigned int rätt variabel att använda i C"?
<p>
Jag testade att köra din algoritm med lite modifikation:
<code>
#define LOOP_MAX 5000000

int main(void)
{
static char result_array[LOOP_MAX];
unsigned int XOR_Tal, antal, pos, i;

for (i = 0; i < LOOP_MAX; ++i) {
XOR_Tal = i % 8192;

for (pos=antal=0;pos < sizeof(XOR_Tal)*8-1; pos++)
antal+=(XOR_Tal>>pos) & 0x01;

result_array[i] = antal;
}

return 0;
}
</code>
Det tog ca 5,6 sekunder att köra ovanstående program på min maskin.

> Sen är jag lite skeptisk till tommys variant... Varför hålla på med arrayer?
> Det skall väl bara tas fram antalet binära ettor?

Att slå upp ett värde i en array är i det här fallet 14 gånger snabbare än att räkna ut det. I alla fall om man jämför din algoritm med min på min gamla burk.

Hej igen Herman.

Använd inte stoppur när du mäter. I C kan du t ex använda clock(). Windows API:et har också andra funktioner för att ta fram tider.

Med clock() ser min kod ut så här, jag skickar ingen exe-fil (har inte din mamma varnat dig för att ta emot exe-filer av främlingar ;-):
<code>
#include <time.h>
#include "file_containing_big_array_mentioned_earlier_in_this_forum.h"

#define LOOP_MAX 5000000

int main(void)
{
static char result_array[LOOP_MAX];
int i, x;
clock_t before;

before = clock();
for (i = 0; i < LOOP_MAX; ++i) {
x = i % 8192;

result_array[i] = bit_count[(x>>8) & 0xff] + bit_count[x & 0xff];
}

printf("Execution time = %f seconds\n",
(float)(clock() - before) / CLOCKS_PER_SEC);

return 0;
}
</code>

När du mätte tiden i ditt VB program körde du då med:
<code>
for y = 0 to 5000000
</code>
så att jämförelsen blir rättvis?

Vad jag menade med unsigned int var bara att Int i VB representeras med 16 bitar, och i C i regel med 32, vilket är det snabbaste.

Om din kod verkligen är 14 gånger snabbare så ger jag mig naturligtvis, men utan att studerat din kod närmare så finns det väl en metod som borde vara ännu snabbare - en union.

struct BitInt
{
unsigned b0 : 1;
//...
}

union Integer
{
int i;
BitInt bi;
}


och använda

Integer talet
talet.i=XOR_Tal;

sum = talet.bi.b0 + talet.bi.b1 + ...

/Niklas Jansson

Jag testade din unionlösning:
<code>
#define LOOP_MAX 5000000

struct bit_int {
unsigned b0 : 1;
unsigned b1 : 1;
unsigned b2 : 1;
unsigned b3 : 1;
unsigned b4 : 1;
unsigned b5 : 1;
unsigned b6 : 1;
unsigned b7 : 1;
unsigned b8 : 1;
unsigned b9 : 1;
unsigned b10 : 1;
unsigned b11 : 1;
unsigned b12 : 1;
};

union integer {
int i;
struct bit_int bit;
};

int main(void)
{
static char result_array[LOOP_MAX];
union integer XOR_Tal;
unsigned int i;

for (i = 0; i < LOOP_MAX; ++i) {
XOR_Tal.i = i % 8192;

result_array[i] =
XOR_Tal.bit.b0 +
XOR_Tal.bit.b1 +
XOR_Tal.bit.b2 +
XOR_Tal.bit.b3 +
XOR_Tal.bit.b4 +
XOR_Tal.bit.b5 +
XOR_Tal.bit.b6 +
XOR_Tal.bit.b7 +
XOR_Tal.bit.b8 +
XOR_Tal.bit.b9 +
XOR_Tal.bit.b10 +
XOR_Tal.bit.b11 +
XOR_Tal.bit.b12;
}

return 0;
}
</code>
Den tar 1.0 sekund på min maskin så min lösning är bara lite mer än dubbelt så snabb.

Niklas jo jag har klippt bort en del det är två arrayer med tal som jag testar mot varandra. If satsen ska igentligen jämföras mot intAntalRattTecken.

Tommy jag försökte efterlikna din kod så mycket som möjligt. Och jag använder en function som jag tror använder api ska kolla på den lite mer(har inte skrivit den själv). Men jag litar inte på det helt och fullt och som sagt vi har olika datorer och olika OS och olika program körandes i bakgrunden. Om du inte vill skicka filen så måste du hålla med om att om du skulle gjort en större loop skulle resultatet bli mer tillförlitligt. Någon annan får gärna också skicka en exe fil plus kod.


ps mamma har gett sig godkänande och jag har just installerat om windows och kör med ett uppdaterat virus skydd och har inte så många statshemligheter och oersättliga saker på datorn. Och jag äger en stor köttig yxa (skämt) ;)