Path: csiph.com!eternal-september.org!feeder.eternal-september.org!reader01.eternal-september.org!.POSTED!not-for-mail From: Tim Rentsch Newsgroups: comp.lang.c Subject: Re: How to use a struct with qsort()? Date: Mon, 04 Nov 2019 16:02:09 -0800 Organization: A noiseless patient Spider Lines: 65 Message-ID: <86h83jfawu.fsf@linuxsc.com> References: <06add10e-1e30-4741-a20c-ff56363733fe@googlegroups.com> <60434cb2-a003-454b-890f-f2121004bd22@googlegroups.com> <1ca42f72-9e0e-40c3-8ef0-b5002e079cef@googlegroups.com> <07784ff9-2fee-49e6-8271-22d713294245@googlegroups.com> Mime-Version: 1.0 Content-Type: text/plain; charset=us-ascii Injection-Info: reader02.eternal-september.org; posting-host="59b683b75f73ead2c1b20aa011ddc5ef"; logging-data="9582"; mail-complaints-to="abuse@eternal-september.org"; posting-account="U2FsdGVkX19Kd96pwyd4WnGDOYS+tI/vKgSqU9q8c2k=" User-Agent: Gnus/5.11 (Gnus v5.11) Emacs/22.4 (gnu/linux) Cancel-Lock: sha1:/FJmH81zDXofsRmWCLyV4ZsaFLo= sha1:qiziXmxobBw1FWuXGxJXxt68kiE= Xref: csiph.com comp.lang.c:147589 Paul writes: > DFS wrote: > >> On 10/19/2019 7:32 PM, already5chosen@yahoo.com wrote: >> >>> On Sunday, October 20, 2019 at 1:27:37 AM UTC+3, DFS wrote: >> >> >>> o.k. I don't know why, but I read your code. >>> Turned out, you don't have an array of records. For some reason, >>> you decided to build an array of pointers to records. That's quite >>> different! >>> Your comparison function should take that into account and to use >>> double indirection, like that: >>> >>> int comparepf(const void *p1, const void *p2) >>> { >>> const struct words *a = *(const struct words **)p1; >>> const struct words *b = *(const struct words **)p2; >>> if (a->wordpf == b->wordpf) >>> return strcmp(a->word, b->word); >>> return a->wordpf < b->wordpf ? -1 : 1; >>> } >> >> The qsort now works. > > I took your code and messed around a bit with it. > > For the prime number idea, you can assign the primes > according to letter frequency. The intention being, > to reduce the amount of storage to hold the prime products. > The letter "e" is assigned "2", as it's the most frequent. > > dichlorodiphenyltrichloroethane 55812442766843314104001446573936360 > > And since that "broke" my calculator, I used log2 of all > the prime numbers and addition, to come up with estimates > of the storage requirements for the "worst word", the one shown. > I had to figure out the storage requirements, so I could > figure out how to store the numbers (I wanted to use uint64_t > initially, but they weren't big enough). > > regmax = 7564585 for string dichlorodiphenyltrichloroethane > > The number is fixed point, and needs to be shifted >>16 to get > the size of register needed. 7564585/65536 = 115.4 or 116 bits, > so two 64 bit uint64_t would do. I multiply together the > primes until one uint64_t is full, then multiply the rest > into a second unit64_t. > > I used GMP, and only transferred my two 64 bit accumulators > to GMP when "most" of the multiplies were finished. [...] With a bit more work you might find a fairly simple encoding that fits in 64 bits and gives a unique value (or very nearly unique) for every anagram. Using the 64-bit encoding as a hash value, put all the words in a big hash table using open addressing for the codes, and a linked list for wordes with a given code, so it's just a few compares on 64-bit values to get to the appropriate anagram family. Hint: one such encoding uses a variation of Ben Bacarisse's idea of using a "histogram" of the number of occurrences of each letter in the alphabet.