Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]
Groups > comp.lang.c > #147522
| From | Ian Collins <ian-news@hotmail.com> |
|---|---|
| Newsgroups | comp.lang.c |
| Subject | Re: So here's a fun challenge |
| Date | 2019-11-03 14:33 +1300 |
| Message-ID | <h26p2rFa2cqU3@mid.individual.net> (permalink) |
| References | <NNgvF.21265$hh5.17108@fx07.iad> |
On 03/11/2019 03:53, DFS wrote:
> Sample output
>
> $ ./randclc 10000000 8 16
>
>
> Item Array 1 Array2
> -------------------------------------------------
> 1 a6HFMQFrnUP0Cnv7 aQPGz0UPCP8gMZHJ
> 2 QQ9JS8SEYk VlcM3nzRa8G
> 3 GdncBWK1 ttPRBRxWj3Hh
> 4 HwSrf8sj9OuYg2RX 3FJOvMAx3bl
> 5 NBntwcDHxL98TNeY HWVU1Ch9wwh
> 6 yJhImP3TCUHDLiLX 345zHvrRz2R
> 7 BYwC64NTlmN 4El6EdqZai1BZH
> 8 7r455Z0miJ3f Tfg2QTH1q
> 9 4aHS68SRsCf0 J1phwTczJCaAOviU
> 10 0WOmIt0FmTY G31XXoCWKKU
> 4999999 rwknQe3j8BmjO3V 5Mp8CqYAGX
> 5000000 XbyWcSJhTfDBGn BPJRhlzsy
> 5000001 These These
> 5000002 are are
> 5000003 the the
> 5000004 dupe dupe
> 5000005 values values
> 5000006 for for
> 5000007 each each
> 5000008 array array
>
> 5.2567s to create 10000000 random string elements (+ add dupes)
> combining... combined arrays 1 and 2
> new unsorted array contains 10000016 elements
> qsorting... 32.7348s
> removing dupes... removed 8 dupes
>
> combined data
> deduped and sorted lowercase
> ---------------------------------
> 1 0000rNRsm
> 2 0002tSS6R
> 3 0003BwtPP1tcD2u6
> 4 0003MzJGcgj2
> 5 0005yUGPLQz
> 6 0007EkZ8GJ4H
> 7 0007muvC2x9w
> 8 000A6GE3
> 9 000crSt5s4MX
> 10 000e8OpCeGvKDA
> 9999999 ZzzYXVSz0Ioz1
> 10000000 zzZzaWh1kOlETZ
> 10000001 ZzzzbgJIE5ao
> 10000002 ZZzzG8RgD3JHA
> 10000003 ZzZzJHAzGc2J
> 10000004 ZZZZkpkDNT
> 10000005 zzzzUF2zlig
> 10000006 ZZzZUt2Pwr
> 10000007 ZzZZxYX10BBKh
> 10000008 zZzZyyIZ
> program ran in 42.8977s seconds
> Done
>
>
> ==========================================================
>
> So 43 seconds on my Window/MSYS2 system for 10,000,000 elements size 8
> to 16. 3/4 of that run time is qsorting the array.
>
> =========================================================================
> For comparison, done in 12 lines of python, plus 2 lines for timing and
> 3 for printing
> =========================================================================
> import sys, random, string, time
> masterTime = time.clock()
>
> randoms1,randoms2 = [],[]
> lo = int(sys.argv[2])
> hi = int(sys.argv[3])
>
> for i in range(int(sys.argv[1])/2):
> randoms1.append(''.join([random.choice(string.ascii_letters +
> string.digits) for x in xrange(random.randint(lo,hi))]))
> randoms2.append(''.join([random.choice(string.ascii_letters +
> string.digits) for x in xrange(random.randint(lo,hi))]))
>
> dupes = ['These','are','the','dupe','values','for','each','array']
> for i in range(len(dupes)):
> randoms1.append(dupes[i])
> randoms2.append(dupes[i])
>
> randsorted = sorted(set(randoms1+randoms2),key=str.lower)
>
> for i in range(len(randsorted)):
> if i<10 or i>len(randsorted)-11:
> print("%2d. %s" % (i+1,randsorted[i]))
>
> print("program ran in: %.3g seconds" %(time.clock()-masterTime))
> =========================================================================
> On my system, this code runs for 37 seconds for 1000000 8 16.
> 8.6x slower than C, but it took maybe 30 minutes to write and test.
Using a slightly modified version of your code in C++ (vector for
arrays, string for the strings), the guts of the combine, sot and dedupe
were:
Strings combined;
combined.reserve(arraySize);
combined.insert( combined.end(), randoms1.begin(), randoms1.end() );
combined.insert( combined.end(), randoms2.begin(), randoms2.end() );
std::sort( combined.begin(), combined.end(), less() );
std::cout << time()-start << "S to sort\n";
start = time();
std::cout << "new sorted array contains " << combined.size() << "
elements\n";
combined.erase(std::unique(combined.begin(), combined.end()),
combined.end());
std::cout << time()-start << "S to dedup\n";
std::cout << "new deduped array contains " << combined.size() << "
elements\n";
Which on my system:
$ g++ -std=c++17 -pedantic -Wextra -Wall -O3 -o fun fun.cpp
$ time ./fun
Item Array 1 Array2
-------------------------------------------------
1 UhyZ4Ex6Sjol xUgSBbJ0d
2 vqF8i6iQQqf kJ3hrdvDoTnv
3 PwaFAx1Q2ZY 8FFoKczj5HB934o
4 iJdX6dtwAkdta i9wOo6QOgMlHLeB
5 QKzTxwXQSn1WH2N 2atg7aVdM6Kobc
6 SMEB90pQ DIvaA8Pt99z6a
7 9MhK1iM50 zsopH4YaDk
8 3iRmiQMe Xet5Olerg4GGnU
9 VPKWiUXc3Epcl2 2QlmL0xP
10 EKNaYyWJd wmijocOEe0w
4999991 EeQ08EVZHkm4hlh Wapv7y34CNNzpAn
4999992 E4KDyvt6FF1MR8 D9QY6eS1HwF
4999993 These These
4999994 are are
4999995 the the
4999996 dupe dupe
4999997 values values
4999998 for for
4999999 each each
5000000 array array
1.26085S to create 10000000 random string elements (+ add dupes)
3.19092S to sort
new sorted array contains 10000000 elements
0.10269S to dedup
new deduped array contains 9999992 elements
0000O3l4xIlD
0002cB9eS3
0002lzVaYmpSH
0007yaIw
000Al1GlOkAfP
000b8bsdj
000ir4XI
000j37ftHAU
000j8SlaN
000JDnZUTsut2tLI
ZZZzN3DyoJU9hOy
ZZZZhpliD
ZzzzgdAwKww
zzZZ4waPKAofj
ZzZYshGXMOzI
zZzyp0NY0
zZzyo7v3
ZzzYLx3l2Nmnc973
zzZydYrs3quxF
ZzZy6FpMdt1Zw
real 0m4.744s
--
Ian.
Back to comp.lang.c | Previous | Next — Previous in thread | Next in thread | Find similar | Unroll thread
So here's a fun challenge DFS <nospam@dfs.com> - 2019-11-02 10:53 -0400
Re: So here's a fun challenge Bart <bc@freeuk.com> - 2019-11-02 17:08 +0000
Re: So here's a fun challenge Richard Damon <Richard@Damon-Family.org> - 2019-11-02 15:01 -0400
Re: So here's a fun challenge Bart <bc@freeuk.com> - 2019-11-02 19:38 +0000
Re: So here's a fun challenge Richard Damon <Richard@Damon-Family.org> - 2019-11-02 16:07 -0400
Re: So here's a fun challenge DFS <nospam@dfs.com> - 2019-11-03 09:29 -0500
Re: So here's a fun challenge Bart <bc@freeuk.com> - 2019-11-02 20:36 +0000
Re: So here's a fun challenge DFS <nospam@dfs.com> - 2019-11-03 09:33 -0500
Re: So here's a fun challenge Paul <nospam@needed.invalid> - 2019-11-03 20:53 -0500
Re: So here's a fun challenge Ian Collins <ian-news@hotmail.com> - 2019-11-03 14:33 +1300
Re: So here's a fun challenge Ian Collins <ian-news@hotmail.com> - 2019-11-03 14:35 +1300
Re: So here's a fun challenge DFS <nospam@dfs.com> - 2019-11-03 00:18 -0400
Re: So here's a fun challenge Ian Collins <ian-news@hotmail.com> - 2019-11-03 18:02 +1300
Re: So here's a fun challenge Bart <bc@freeuk.com> - 2019-11-03 11:19 +0000
Re: So here's a fun challenge Ian Collins <ian-news@hotmail.com> - 2019-11-04 00:33 +1300
Re: So here's a fun challenge DFS <nospam@dfs.com> - 2019-11-03 09:39 -0500
Re: So here's a fun challenge Autist <autist69@gmail.com> - 2019-11-03 11:16 +0100
Re: So here's a fun challenge Autist <autist69@gmail.com> - 2019-11-03 11:29 +0100
Re: So here's a fun challenge Ian Collins <ian-news@hotmail.com> - 2019-11-03 23:34 +1300
Re: So here's a fun challenge Melzzzzz <Melzzzzz@zzzzz.com> - 2019-11-03 11:04 +0000
Re: So here's a fun challenge Autist <autist69@gmail.com> - 2019-11-03 14:56 +0100
Re: So here's a fun challenge Autist <autist69@gmail.com> - 2019-11-03 15:36 +0100
Re: So here's a fun challenge nobody@example.org (Scott) - 2019-11-03 17:35 +0000
Re: So here's a fun challenge Ian Collins <ian-news@hotmail.com> - 2019-11-04 08:03 +1300
Re: So here's a fun challenge DFS <nospam@dfs.com> - 2019-11-04 10:07 -0500
Re: So here's a fun challenge nobody@example.org (Scott) - 2019-11-04 16:06 +0000
Re: So here's a fun challenge DFS <nospam@dfs.com> - 2019-11-04 15:33 -0500
csiph-web