Print

Please login or register.
1 Hour 1 Day 1 Week 1 Month Forever
Login with username, password and session length

[3man75]

UML help. I'm trying to write this before the deadline now that my actual program is completed. It's thankfully extra credit but I'm having trouble over what I put where.

Specifically If I have a constructor with one more parameters how would I write them? Everything else I think is okay but i'm not sure.

[TheBiggerFish]

Okay, how even DOES big-O notation work, and what is it for radix sort?  It's APPARENTLY O(wn), but w just isn't making any sense and I've even heard it said that that's not even a valid...Thing.

....

while(true){this.out.textToSpeech("AAA");}

[Putnam]

big O notation is the asymptotic growth profile of the worst case of a given algorithm; "n" usually refers to the size of the input.

O(n²) means that the growth profile of the worst case scenario is n². It could be 1,000,000n², and it'd still be O(n²), since it's asymptotic (and 1,000,000 barely makes a dent on 10¹⁰¹⁰⁰²).

Radix sort is O(wn), where w is the word size of the keys to be sorted. w can be treated as a constant AFAIK, since you're probably not increasing word size when you increase array size (I.E. an array of 32-bit integers won't suddenly become an array of 64-bit integers when you quadruple the size of the array), which is why it may be preferable over O(nlogn) algorithms such as mergesort or quicksort.

[TheBiggerFish]

I keep getting mixed signals on w being constant,  though.  I blame Wikipedia but seriously.

[Putnam]

OHOOHH

yeah it's right, the size of the keys, not the values, i'm dumb

yeah, if you have 8 keys the key is going to be 3 bits, 16 keys 4 bits etc.

[TheBiggerFish]

Aha.  Thankye.

_{AAAARGH I HAVE TO EDIT THAT NOW RRRRRRGH.}

[Reelya]

For Radix sort, it looks at things on a per-symbol basis, so it doesn't have to be binary-based. It can be base 10, or you can use it for sorting words on a base-26 system. "w" is the average number of symbols per "word" in your input data, hence why it's not a normal constant. For example if your sorting words, then w is the average number of letters in your input words, e.g. 3.6 letters per word.

In other words, whether radix sort is better or worse than an O(N log N) algorithm would be a matter of whether the average word-length is less than or greater than log₂N (the efficiency of the best binary-based sorts). Hence, Radix sort is best at sorting a large number of short keys.

[Putnam]

Yeah, but the minimum for w is log(n), AFAIK. There's no way to store keys with less data.

[Reelya]

But the algorithm only does an operation per-symbol.

e.g. if you input the integer "102" it processes the 1, the 0 then the 2. If all your inputs are three-digit numbers, then w is three, regardless of how many numbers you are sorting, and regardless of what data type you use to store them.

EDIT: I improved my understanding of radix sort just now. Basically, you do an O(N) sort into bins. If the base is 10 you sort your values into 10 bins based on the lowest value decimal place. Then you take the values out of those bins in order, and put them into another 10 bins, but based on their 10's values. Then you take the ones sorted by 10's values, and again transfer them into 10 bins based on their 100's value. That's three passes of an O(N) algorithm, for a fully sorted list. Hence "w" is 3, and the overall algorithm has order O(WN).

https://www.cs.auckland.ac.nz/software/AlgAnim/radixsort.html

Basically, if there are a large number of keys to sort, or the length of the keys is relatively short, radix sort becomes very effective compared to comparison-based sorts.

[Gatleos]

Mind sharing it when it's done? I know I'd like it.

Source is right here. The code is still a bit rough, and you'll need to get this and this installed... and use Python 2.x

I wish installing dependencies was easier on windows.

[Bumber]

Mind sharing it when it's done? I know I'd like it.

Source is right here. The code is still a bit rough, and you'll need to get this and this installed... and use Python 2.x

I wish installing dependencies was easier on windows.

Couldn't you use pip with a requirements file?

[Gatleos]

Couldn't you use pip with a requirements file?

Yeah, I remembered pip right after I posted that. Can't seem to find a repository for that win32gui module, though.

[Mephisto]

Yeah, I remembered pip right after I posted that. Can't seem to find a repository for that win32gui module, though.

https://pypi.python.org/pypi/pypiwin32

[nogoodnames]

Does anyone know a good web API to send a message from one phone (specifically a Windows phone) to another without requiring user intervention?

[Gatleos]

Yeah, I remembered pip right after I posted that. Can't seem to find a repository for that win32gui module, though.

https://pypi.python.org/pypi/pypiwin32

...And it had a slightly different name than what I searched for. Thanks!