Skip to content

Instantly share code, notes, and snippets.

@serenaf
Created May 17, 2015
Embed
What would you like to do?
TopN integer
955
991
625
76
881
105
570
533
518
180
336
251
785
977
53
396
946
185
128
818
487
947
788
525
511
385
725
203
224
267
607
588
356
120
47
140
77
465
165
76
605
338
852
582
212
471
360
441
441
651
320
551
963
541
642
253
623
223
314
809
638
858
832
351
377
585
13
357
29
315
424
467
589
468
126
564
637
855
299
460
234
22
12
511
568
773
384
725
16
981
903
719
690
544
990
532
36
77
792
180
768
880
153
30
229
900
840
612
56
50
464
121
14
245
440
213
185
337
775
344
356
409
112
299
473
613
130
887
862
720
603
248
716
250
29
353
93
207
456
819
78
805
32
389
411
153
396
810
250
416
919
223
173
63
663
129
824
114
501
416
570
94
520
270
79
986
121
600
161
174
878
221
196
194
983
433
266
120
357
102
282
198
587
954
880
692
235
929
148
542
176
468
143
784
636
951
538
657
507
809
473
891
847
215
385
278
223
606
334
485
243
748
295
580
942
357
9
838
998
336
605
50
311
901
348
256
696
480
231
967
901
776
27
953
329
137
446
727
558
247
448
658
806
631
270
990
762
379
808
724
183
980
173
347
190
150
575
544
72
327
91
476
457
966
268
121
790
4
191
562
450
111
648
955
149
890
442
856
236
183
188
553
634
393
333
957
804
53
409
15
139
749
434
680
11
971
960
373
180
198
596
378
205
606
78
731
389
326
202
975
90
954
77
389
670
360
531
184
733
167
216
905
780
339
646
727
102
724
978
68
10
733
105
763
107
5
438
277
168
146
476
723
426
62
52
86
394
677
547
116
183
201
921
289
796
985
755
437
577
469
579
826
262
33
838
820
925
852
657
63
745
329
765
995
623
729
966
960
520
951
895
699
929
320
542
544
711
669
617
783
37
796
222
324
750
184
339
562
560
893
775
271
946
162
75
195
482
239
477
763
668
93
777
979
968
674
325
885
877
100
779
345
29
391
36
935
244
242
208
939
876
782
179
472
936
160
902
478
232
920
325
41
26
248
647
189
765
976
705
727
230
81
716
5
103
801
627
420
509
65
139
674
113
305
555
443
255
783
315
644
461
126
750
564
182
277
280
451
641
884
224
154
245
875
565
891
16
407
891
527
470
218
234
907
643
852
466
446
885
31
490
211
733
286
161
702
391
381
699
250
534
782
798
341
892
136
946
529
85
939
626
493
282
50
583
337
327
4
640
167
564
844
67
155
736
972
911
130
782
520
201
931
304
137
676
283
832
441
392
549
398
806
158
550
281
785
65
754
173
944
251
440
272
130
183
57
972
830
708
652
381
506
466
225
630
530
793
560
824
879
653
700
281
698
986
381
871
759
264
906
785
27
985
610
43
401
642
713
310
961
162
697
352
867
250
905
475
87
275
723
442
687
338
80
930
261
549
743
702
202
551
930
604
994
152
305
455
720
710
446
281
860
146
156
304
782
946
956
278
57
540
106
221
840
5
728
829
868
312
678
113
524
696
929
408
79
108
474
703
408
366
105
836
625
949
88
948
257
25
545
232
44
421
466
557
242
379
938
968
851
706
476
489
433
616
913
893
580
933
17
13
59
347
544
255
149
677
993
700
705
600
387
17
386
841
473
283
696
805
482
401
898
237
349
175
508
540
882
561
757
3
170
949
771
123
722
910
781
309
460
803
434
729
363
647
998
441
296
89
153
845
843
859
552
59
120
533
163
29
422
272
237
195
78
569
496
423
951
7
629
641
515
761
914
5
616
639
294
751
692
53
857
402
475
884
757
507
118
464
851
309
700
110
931
945
683
33
4
636
628
526
331
293
515
522
241
497
631
919
364
551
699
508
827
270
315
911
895
647
794
566
319
837
775
994
87
990
935
298
556
538
995
665
966
128
367
360
669
325
487
580
846
884
280
581
748
718
500
766
348
198
491
385
119
254
328
459
578
158
750
240
452
68
898
256
403
211
819
203
87
208
995
909
65
844
654
481
809
525
102
525
470
510
91
2
794
833
535
408
12
742
378
535
716
100
976
601
307
350
981
835
671
723
13
503
561
643
180
554
408
14
215
947
182
612
75
370
0
865
615
686
27
797
521
546
473
915
548
737
619
894
757
117
3
497
668
117
749
368
60
65
212
556
902
658
849
924
406
638
669
63
816
768
388
771
567
45
21
414
148
588
648
918
131
465
776
327
874
742
592
777
62
928
750
801
734
502
525
561
325
337
831
141
788
518
519
549
90
709
64
672
859
853
129
453
676
761
870
664
669
800
365
771
70
617
464
557
153
951
790
def file_gen(file_name):
with open(file_name, 'r') as f:
for line in f:
yield int(line)
def test_gen( n ):
for x in range( 0, n ):
yield x
def topn(gen, n):
result = []
test = []
""" read in line by line """
for x in gen:
test.append( x)
""" if result array is still smaller than n just append the next number """
if(len(result) < n):
result.append(x)
""" if n numbers are read in sort the array"""
if(len(result) ==n):
result.sort()
""" if already n numbers have been read in, take the next number and compare with minimum (a[0]) """
elif( len( result ) == n and result[0] < x ):
result.append( x )
result.sort();
""" get rid of the old minimum"""
result.pop( 0 )
result.sort()
""" return the array in descending sorted order """
result.reverse()
return result
def main():
gen = file_gen( 'numbers.txt' )
# gen = test_gen( 10000 )
r = topn( gen, 10 )
for x in range( 0, len( r ) ):
print(r[x])
if __name__ == '__main__':
main()
import unittest
from topn import topn, test_gen
class TopnTests(unittest.TestCase):
""" an empty list should return no elements """
def testEmptyList(self):
gen = test_gen( 0 )
r = topn( gen, 1 )
self.assertEqual(len(r), 0)
""" a list that has smaller than n value just returns all its values"""
def testListSmallerN(self):
gen = test_gen( 1 )
r = topn( gen, 2 )
self.assertEqual(len(r), 1)
""" a list containing less than n elements just returns all its elements sorted """
def testListSmallerNValue(self):
gen = test_gen( 4 )
r = topn( gen, 1 )
self.assertEqual(r[0], 3)
""" a list containing more than n elements returns n elements """
def testListLargerN(self):
gen = test_gen( 5 )
r = topn( gen, 2 )
self.assertEqual(len(r), 2)
def main():
unittest.main()
if __name__ == '__main__':
main()
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment