• Log InLog In
  • Register
Liquid`
Team Liquid Liquipedia
EDT 09:22
CEST 15:22
KST 22:22
  • Home
  • Forum
  • Calendar
  • Streams
  • Liquipedia
  • Features
  • Store
  • EPT
  • TL+
  • StarCraft 2
  • Brood War
  • Smash
  • Heroes
  • Counter-Strike
  • Overwatch
  • Liquibet
  • Fantasy StarCraft
  • TLPD
  • StarCraft 2
  • Brood War
  • Blogs
Forum Sidebar
Events/Features
News
Featured News
[ASL20] Ro24 Preview Pt1: Runway132v2 & SC: Evo Complete: Weekend Double Feature4Team Liquid Map Contest #21 - Presented by Monster Energy9uThermal's 2v2 Tour: $15,000 Main Event18Serral wins EWC 202549
Community News
Maestros of The Game—$20k event w/ live finals in Paris23Weekly Cups (Aug 11-17): MaxPax triples again!13Weekly Cups (Aug 4-10): MaxPax wins a triple6SC2's Safe House 2 - October 18 & 195Weekly Cups (Jul 28-Aug 3): herO doubles up6
StarCraft 2
General
What mix of new and old maps do you want in the next 1v1 ladder pool? (SC2) : 2v2 & SC: Evo Complete: Weekend Double Feature Geoff 'iNcontroL' Robinson has passed away The GOAT ranking of GOAT rankings RSL Revival patreon money discussion thread
Tourneys
RSL: Revival, a new crowdfunded tournament series Maestros of The Game—$20k event w/ live finals in Paris Sparkling Tuna Cup - Weekly Open Tournament Monday Nights Weeklies Master Swan Open (Global Bronze-Master 2)
Strategy
Custom Maps
External Content
Mutation # 487 Think Fast Mutation # 486 Watch the Skies Mutation # 485 Death from Below Mutation # 484 Magnetic Pull
Brood War
General
Flash On His 2010 "God" Form, Mind Games, vs JD BGH Auto Balance -> http://bghmmr.eu/ Joined effort New season has just come in ladder BW General Discussion
Tourneys
[ASL20] Ro24 Group B [ASL20] Ro24 Group C BWCL Season 63 Announcement [CSLPRO] It's CSLAN Season! - Last Chance
Strategy
Simple Questions, Simple Answers Fighting Spirit mining rates [G] Mineral Boosting Muta micro map competition
Other Games
General Games
Nintendo Switch Thread General RTS Discussion Thread Dawn of War IV Path of Exile Stormgate/Frost Giant Megathread
Dota 2
Official 'what is Dota anymore' discussion
League of Legends
Heroes of the Storm
Simple Questions, Simple Answers Heroes of the Storm 2.0
Hearthstone
Heroes of StarCraft mini-set
TL Mafia
TL Mafia Community Thread Vanilla Mini Mafia
Community
General
US Politics Mega-thread Russo-Ukrainian War Thread The year 2050 Things Aren’t Peaceful in Palestine European Politico-economics QA Mega-thread
Fan Clubs
INnoVation Fan Club SKT1 Classic Fan Club!
Media & Entertainment
Anime Discussion Thread Movie Discussion! [Manga] One Piece [\m/] Heavy Metal Thread
Sports
2024 - 2026 Football Thread TeamLiquid Health and Fitness Initiative For 2023 Formula 1 Discussion
World Cup 2022
Tech Support
High temperatures on bridge(s) Gtx660 graphics card replacement Installation of Windows 10 suck at "just a moment"
TL Community
The Automated Ban List TeamLiquid Team Shirt On Sale
Blogs
Evil Gacha Games and the…
ffswowsucks
Breaking the Meta: Non-Stand…
TrAiDoS
INDEPENDIENTE LA CTM
XenOsky
[Girl blog} My fema…
artosisisthebest
Sharpening the Filtration…
frozenclaw
ASL S20 English Commentary…
namkraft
Customize Sidebar...

Website Feedback

Closed Threads



Active: 2197 users

The Big Programming Thread - Page 341

Forum Index > General Forum
Post a Reply
Prev 1 339 340 341 342 343 1031 Next
Thread Rules
1. This is not a "do my homework for me" thread. If you have specific questions, ask, but don't post an assignment or homework problem and expect an exact solution.
2. No recruiting for your cockamamie projects (you won't replace facebook with 3 dudes you found on the internet and $20)
3. If you can't articulate why a language is bad, don't start slinging shit about it. Just remember that nothing is worse than making CSS IE6 compatible.
4. Use [code] tags to format code blocks.
spinesheath
Profile Blog Joined June 2009
Germany8679 Posts
August 11 2013 16:31 GMT
#6801
There are databases like Microsoft's SQL Server Compact which don't require a seperate database system, it's integrated into the program executable. Of course those are a bit more limited than standalone database systems, but unless you work with large amounts of data that shouldn't be an issue.

Also you might be able to easily separate your data management from your other code through an interface which makes it easy to switch between the different implementations (database, even different database systems, and what are going to use at first).
If you have a good reason to disagree with the above, please tell me. Thank you.
Shield
Profile Blog Joined August 2009
Bulgaria4824 Posts
Last Edited: 2013-08-11 19:11:22
August 11 2013 17:06 GMT
#6802
On August 11 2013 20:24 one-one-one wrote:
Show nested quote +
On August 11 2013 19:17 spinesheath wrote:
How about we just make everyone happy and actually specify what N is whenever we write O(f(N))?

If N is the length/height of the image, it's O(N^2), if N is the number of pixels, it's O(N), and if we assume a fixed image size it's O(1).

Saying something is O(f(N)) without specifying N is nonsense anyways. You usually can't omit it "because it's obvious" because there are many possible interpretations (as shown above).


Yeah.

It is also important to not bring up asymptotic complexity when uncalled for.

This is a programming thread.
In most cases you care about raw performance. To express yourself in more fine grained terms you might use execution time, number of instructions, etc. which might be depend on one or more variable quantities.

When saying that something is O(n) or O(n log n), or whatever, you have most certainly made a number of idealizations that don't reflect how a modern computer actually works.
So instead of worrying about theoretical complexity you should focus on writing simple, reasonable code with good cache access patterns.

Or in the words of Linus Torvalds:
https://lkml.org/lkml/2008/5/7/456


Honestly, I wouldn't rely on any of Torvalds' sayings about programming. He has already proven to be quite radical in this field by declaring C++ as bs. You can't teach an old dog new tricks. ^^

The guy may be well recognised and all for his Linux, but that doesn't make him an always-right hero.

Edit: I'd like to practise and enhance my programming skills, so I'm thinking what program to do. However, I can't think of anything that would be at least a little bit useful. Could you give me ideas? I'm not looking for something super time-consuming, but I want it to be challenging and fun. I'm going to use Java as a programming language.

It would be nice if I use data structure that isn't array. It'd be nice if I try generics (C++ templates) as well. I'm still thinking what to do, but I hope for some ideas.

Edit #2: OnlineJudge seems like a silly useless thing imho, so I'd rather avoid practising on that.
FunkyLich
Profile Blog Joined August 2010
United States107 Posts
August 11 2013 21:03 GMT
#6803
Why would you take that one statement from Linus and just automatically assume that he thinks order complexity is a bunch of BS? I think the takeaway should be that if you are coding for performance you need to be cognizant of how the hardware works, and that CODE is not automatically faster because it implements an algorithm with superior asymptotic time complexity i.e. O(n) vs O(1). There are many other factors to take into account when considering what the true performance will be, namely caching, as others have mentioned.

For those of you who are in college and just learning this big O notation stuff, don't go away thinking this is all useless BS theory. Order notation refers to asymptotic time complexity. It answers the question: "For varying input size N, what is the end behavior of the graph T(N), where T(N) is how long the algorithm takes to execute". End behavior is the key word. That means it is most useful for reasoning about large values of N.

Most of the time, when doing performance computing, we can make assumptions about the maximum size of N, which may forgo the need for heavier duty algorithms. For example, insertion sort (O(n^2) worst case) is faster than quick sort for very small N, so if you need to sort a thousand arrays of size 10, you should use that instead of quicksort (O(nlogn)). The point is that order notation is a useful performance consideration, but it is far from the being the only. Remember, order complexity ignores differences that can be expressed as a constant factor. So, when an algorithm that is ""only"" at most 100 times faster than another, they are treated with the same big O notation. An algorithm with bad asymptotic complexity is the kind of performance problem that will make the difference between coming back from lunch and the program having finished, and the program tying up your computer for 2 weeks. People who do performance computing generally take this stuff for granted, and are thinking about much more fine-tuned optimizations.

Having said that, I want to share a few good model cases I've experienced where order notation is utterly useless.

Caching and matrix multiplication:
+ Show Spoiler +

Matrix multiplication is probably one of the best ways to demonstrate the penalties imposed by a cache miss. Just to keep it simple, the result of multiplying an NxN matrix A with an NxN matrix B will produce an NxN matrix C by finding the dot product with the corresponding rows of A and columns of B.
For a better explanation: Matrix Multiplication

This means that in our program, we will need to pull data by traversing A by row, and B by column. What does that look like in memory?

This is what a traversal by row looks like in memory, each "v" marks a step in the traversal:
v-------v-------v------v------v------v-------v------v------v--...
[0,0] [1,0] [2,0] [3,0] [4,0] [5,0] [6,0] [7,0] [0,1]

and traversal by column:
v-------------------------------------------------------------v-----...
[0,0] [1,0] [2,0] [3,0] [4,0] [5,0] [6,0] [7,0] [0,1] [1,1] [2,1] [3,1] [4,1] [5,1] [6,1] [7,1]
Doesn't make sense? See row-major order

If you are familiar with one of the fundamental rules of processor caching, principle of locality, you know this column traversal is going to be the source of lots of systematic cache misses, which are bad. The processor generally caches contiguous memory, memory that's close together. How can it possibly know to cache something that may be a thousand addresses ahead? The remedy for this is to store the inverse of B instead. This way we can traverse B by row and treat the rows as columns.

When I did this experiment, it was for a parallel and distributed computing course. The goal of the assignment was to implement a parallel matrix multiplier on SRAM (shared memory), in such a way that the processors would not be competing for resources. So we did this complex stuff to make sure they were staggered and everything, and did some performance tests (with timers), to find very minimal, almost nonexistent gains. Then we tried with an inverted B matrix, and the difference was hilarious (I think it was something like 2x speed up). It was a huge performance boost just for paying a little bit of attention to caching, and stupidly easy to code too.


Slow O(n) Radix sort:

+ Show Spoiler +

For those not familiar with radix sort, it is a theoretically interesting sorting algorithm because it has linear O(n) time complexity (sort of), and space complexity isn't terrible. Here is a simple example of a radix sort. The gist is that you impose an arbitrary base on the integer elements, say 10 (it's usually much higher). And you sort the numbers one digit at a time, starting from left to right:

123 900 900 900
223 536 536 537
537 537 537 536
536 223 256 256
256 256 223 256
900 123 123 123

This is a gross simplification because I am obviously using some auxillary sort on each step (and we're using the MSD(most significant digit) variant cause it's easiest to understand). But since each step only sorts on one digit we can use a bucket sort or counting sort with linear complexity. Radix sort looks really good on paper, and it is fast. But in spite of being linear, it's not as fast as you'd think. A large constant is imposed on its time complexity mostly from the heavy use of division and modulus. So even for large N it doesn't fair a whole lot better than plain old quicksort. When implementing it, I used the LSD variant, and compared it to quicksort, which is asymptotically inferior. If I remember correctly, the radix sort only barely edged out the quicksort even with very large N and picking an optimum base (our example used base 10, the fastest base for me was in the 200s).


So for those of you still learning the ropes--I know I am--try to expose yourself to some good experimental computer science. Personally, I consider myself a theory guy, and my first experience with real hard core performance computing didn't happen till the last semester of my senior year, and it changed the way I think about computing. After you get your fill of basic theory, start getting your feet wet with experiments. Try implementing an algorithm and use clever caching to get some quantifiable speed up. It will open up your world just a little bit.
obesechicken13
Profile Blog Joined July 2008
United States10467 Posts
Last Edited: 2013-08-11 21:13:55
August 11 2013 21:13 GMT
#6804
On August 12 2013 01:03 Morfildur wrote:
Show nested quote +
On August 12 2013 00:51 obesechicken13 wrote:
I need some help deciding whether to use a linked list or a dynamic array (or some other data structure).

Basically I have a config file that looks like this:

cat1
item1
item2
item3
#comment
cat2
item1
item2
....
catN
item1
...
itemN

+ Show Spoiler +

Eventually I'll consider putting this in a db, though if I want the program I'm making to be shareable I may keep it like this since not everyone has MySQL installed on their machines.

I read the program in line by line, and right now I want a way to manipulate the contents of the config file.
Obviously, while I'm the only one using the program, I can edit the config file by hand and restart the app. But in the future if I want to share it, it'd be nice to give people a gui to edit and use the file dynamically.
[image loading]


I'm just not sure if this is the best approach. Maybe there's a simpler solution? Maybe Linked lists fail to address a performance issue?


How many items are in the config file?
The correct answer is most likely: It does not matter, just pick the easy solution.

I usually go with a Dictionary/Associative array of arrays, e.g. (C#) "Dictionary<String, List<String>>" or something similar.

I looked into dictionaries. I don't think they'll work, but thanks for the suggestions.

I think I'll try out a list of objects. Linked lists are hard to get my head around.
I think in our modern age technology has evolved to become more addictive. The things that don't give us pleasure aren't used as much. Work was never meant to be fun, but doing it makes us happier in the long run.
one-one-one
Profile Joined November 2011
Sweden551 Posts
August 11 2013 22:13 GMT
#6805
On August 12 2013 06:03 FunkyLich wrote:
Why would you take that one statement from Linus and just automatically assume that he thinks order complexity is a bunch of BS? I think the takeaway should be that if you are coding for performance you need to be cognizant of how the hardware works, and that CODE is not automatically faster because it implements an algorithm with superior asymptotic time complexity i.e. O(n) vs O(1). There are many other factors to take into account when considering what the true performance will be, namely caching, as others have mentioned.

For those of you who are in college and just learning this big O notation stuff, don't go away thinking this is all useless BS theory. Order notation refers to asymptotic time complexity. It answers the question: "For varying input size N, what is the end behavior of the graph T(N), where T(N) is how long the algorithm takes to execute". End behavior is the key word. That means it is most useful for reasoning about large values of N.

Most of the time, when doing performance computing, we can make assumptions about the maximum size of N, which may forgo the need for heavier duty algorithms. For example, insertion sort (O(n^2) worst case) is faster than quick sort for very small N, so if you need to sort a thousand arrays of size 10, you should use that instead of quicksort (O(nlogn)). The point is that order notation is a useful performance consideration, but it is far from the being the only. Remember, order complexity ignores differences that can be expressed as a constant factor. So, when an algorithm that is ""only"" at most 100 times faster than another, they are treated with the same big O notation. An algorithm with bad asymptotic complexity is the kind of performance problem that will make the difference between coming back from lunch and the program having finished, and the program tying up your computer for 2 weeks. People who do performance computing generally take this stuff for granted, and are thinking about much more fine-tuned optimizations.

Having said that, I want to share a few good model cases I've experienced where order notation is utterly useless.

Caching and matrix multiplication:
+ Show Spoiler +

Matrix multiplication is probably one of the best ways to demonstrate the penalties imposed by a cache miss. Just to keep it simple, the result of multiplying an NxN matrix A with an NxN matrix B will produce an NxN matrix C by finding the dot product with the corresponding rows of A and columns of B.
For a better explanation: Matrix Multiplication

This means that in our program, we will need to pull data by traversing A by row, and B by column. What does that look like in memory?

This is what a traversal by row looks like in memory, each "v" marks a step in the traversal:
v-------v-------v------v------v------v-------v------v------v--...
[0,0] [1,0] [2,0] [3,0] [4,0] [5,0] [6,0] [7,0] [0,1]

and traversal by column:
v-------------------------------------------------------------v-----...
[0,0] [1,0] [2,0] [3,0] [4,0] [5,0] [6,0] [7,0] [0,1] [1,1] [2,1] [3,1] [4,1] [5,1] [6,1] [7,1]
Doesn't make sense? See row-major order

If you are familiar with one of the fundamental rules of processor caching, principle of locality, you know this column traversal is going to be the source of lots of systematic cache misses, which are bad. The processor generally caches contiguous memory, memory that's close together. How can it possibly know to cache something that may be a thousand addresses ahead? The remedy for this is to store the inverse of B instead. This way we can traverse B by row and treat the rows as columns.

When I did this experiment, it was for a parallel and distributed computing course. The goal of the assignment was to implement a parallel matrix multiplier on SRAM (shared memory), in such a way that the processors would not be competing for resources. So we did this complex stuff to make sure they were staggered and everything, and did some performance tests (with timers), to find very minimal, almost nonexistent gains. Then we tried with an inverted B matrix, and the difference was hilarious (I think it was something like 2x speed up). It was a huge performance boost just for paying a little bit of attention to caching, and stupidly easy to code too.


Slow O(n) Radix sort:

+ Show Spoiler +

For those not familiar with radix sort, it is a theoretically interesting sorting algorithm because it has linear O(n) time complexity (sort of), and space complexity isn't terrible. Here is a simple example of a radix sort. The gist is that you impose an arbitrary base on the integer elements, say 10 (it's usually much higher). And you sort the numbers one digit at a time, starting from left to right:

123 900 900 900
223 536 536 537
537 537 537 536
536 223 256 256
256 256 223 256
900 123 123 123

This is a gross simplification because I am obviously using some auxillary sort on each step (and we're using the MSD(most significant digit) variant cause it's easiest to understand). But since each step only sorts on one digit we can use a bucket sort or counting sort with linear complexity. Radix sort looks really good on paper, and it is fast. But in spite of being linear, it's not as fast as you'd think. A large constant is imposed on its time complexity mostly from the heavy use of division and modulus. So even for large N it doesn't fair a whole lot better than plain old quicksort. When implementing it, I used the LSD variant, and compared it to quicksort, which is asymptotically inferior. If I remember correctly, the radix sort only barely edged out the quicksort even with very large N and picking an optimum base (our example used base 10, the fastest base for me was in the 200s).


So for those of you still learning the ropes--I know I am--try to expose yourself to some good experimental computer science. Personally, I consider myself a theory guy, and my first experience with real hard core performance computing didn't happen till the last semester of my senior year, and it changed the way I think about computing. After you get your fill of basic theory, start getting your feet wet with experiments. Try implementing an algorithm and use clever caching to get some quantifiable speed up. It will open up your world just a little bit.


Interesting. Your entire post is just reiterating stuff I already said in a much more verbose format.
You are mostly correct, but did you actually make an effort to understand what I wrote?
I already mentioned the aspects about asymptotic behavior and cache locality.

The point about the quote from Linus was that it is overly simplistic to think about O(1) functions as cheap to execute on a real computer. As we have already concluded, something could be considered O(n^2) or O(1) depending on what is variable, albeit while causing some confusion to some people here.

In the Linux kernel example a developer said: "The sort time on an 8k array runs in constant time".
This is true in the sense that the sorting algorithm is invoked on a bounded size array which requires a bounded amount of time to execute with any sane sorting algorithm.
Linus point is that 8k might still be a freaking large array to sort. What matters here is not the actual complexity,
but total time required to execute.

So the point about including that quote was to show that this misuse of big O notation is quite common due to programmers not having a solid enough grasp of what the concept actually means.
Hell, even Linux kernel developers get it wrong.

So yes, if used in the wrong way, complexity notation is just a bunch of BS in actual programming.

I'm NOT saying complexity notation is a bunch of BS in general.
Why would I do that when I explicitly wrote that I studied computer science at university?
http://www.youtube.com/watch?feature=player_embedded&v=1BFY4R7IIP4#t=1710s
Shield
Profile Blog Joined August 2009
Bulgaria4824 Posts
August 11 2013 22:50 GMT
#6806
Most of us here have studied Computer Science or a branch of it, so you don't have to show off. You may also better your behaviour as one of the guys here has pointed out.

There is no confusion about Big O. Just because some guy writes crappy code with no variables doesn't mean we don't know Big O. If his code was better written, then it would have been O(n^2). Magic numbers are bad.
FunkyLich
Profile Blog Joined August 2010
United States107 Posts
Last Edited: 2013-08-12 01:28:13
August 12 2013 01:20 GMT
#6807
On August 12 2013 07:13 one-one-one wrote:
Interesting. Your entire post is just reiterating stuff I already said in a much more verbose format.

I guess this is one way of saying you agree with me, albeit stripping my post of all novelty. I'll take what I can get.

On August 12 2013 07:13 one-one-one wrote:
You are mostly correct, but did you actually make an effort to understand what I wrote?

Candidly, no. Sorry. I tend to just read things at face value out of context. And no I didn't read anything else you said because I'm lazy and pig-headed. [/not being sarcastic]

On August 12 2013 07:13 one-one-one wrote:
I already mentioned the aspects about asymptotic behavior and cache locality.

My impression was that this thread was mostly supposed to be a place for aspiring programmers to learn programming from those who've been doing it for a while, and a place for programmers to discuss programming. My post was taking the former approach. The point was not to argue really, it was just to give me a reason to drop a knowledge bomb... and show off, cause that's just how I get my fix.

edit:
On an entirely different note:
Is anyone here a prolog user, or interested in prolog/declaritive programming/deductive databases?
Deleted User 101379
Profile Blog Joined August 2010
4849 Posts
August 12 2013 02:26 GMT
#6808
On August 12 2013 07:50 darkness wrote:
Most of us here have studied Computer Science or a branch of it, so you don't have to show off. You may also better your behaviour as one of the guys here has pointed out.

There is no confusion about Big O. Just because some guy writes crappy code with no variables doesn't mean we don't know Big O. If his code was better written, then it would have been O(n^2). Magic numbers are bad.


The confusion is:

void foo()
{
for (int i = 0; i < 2; ++i) do_stuff();
}

void bar()
{
do_stuff();
do_stuff();
}


Why should foo() be O(N) and bar() O(1) eventhough calling them always uses a constant amount of time since they do not change depending on their input?
waxypants
Profile Blog Joined September 2009
United States479 Posts
August 12 2013 02:52 GMT
#6809
On August 12 2013 07:50 darkness wrote:
Most of us here have studied Computer Science or a branch of it, so you don't have to show off. You may also better your behaviour as one of the guys here has pointed out.

There is no confusion about Big O. Just because some guy writes crappy code with no variables doesn't mean we don't know Big O. If his code was better written, then it would have been O(n^2). Magic numbers are bad.


How can you speak for everybody? Not everybody is wrong, but there has been some pretty obvious confusion using Big O going on here.
Shield
Profile Blog Joined August 2009
Bulgaria4824 Posts
Last Edited: 2013-08-12 03:11:44
August 12 2013 02:57 GMT
#6810
On August 12 2013 11:26 Morfildur wrote:
Show nested quote +
On August 12 2013 07:50 darkness wrote:
Most of us here have studied Computer Science or a branch of it, so you don't have to show off. You may also better your behaviour as one of the guys here has pointed out.

There is no confusion about Big O. Just because some guy writes crappy code with no variables doesn't mean we don't know Big O. If his code was better written, then it would have been O(n^2). Magic numbers are bad.


The confusion is:

void foo()
{
for (int i = 0; i < 2; ++i) do_stuff();
}

void bar()
{
do_stuff();
do_stuff();
}


Why should foo() be O(N) and bar() O(1) eventhough calling them always uses a constant amount of time since they do not change depending on their input?


This is a tricky question, but I guess because '2' is (sort of) considered as a variable. You change it to "10", you have do_stuff() 10 times. On the other hand, you can't change just 1 variable/number/thing in bar() to have do_stuff() executed more than twice.

The confusion may be about if you agree to imagine "2" as a variable instead of a number.

I may be wrong, but this is just my thinking.

Edit: If you really think about semantics of "constant", you really shouldn't be able to change the value. However, you can change it in the for loop case, so it's not really constant imho. It's what O(1) stands for: wikipedia

Edit #2: On the other hand, constant time's definition says if you don't rely on input, then it's constant time. O(N)

http://en.wikipedia.org/wiki/Time_complexity#Constant_time
spinesheath
Profile Blog Joined June 2009
Germany8679 Posts
August 12 2013 06:09 GMT
#6811
On August 12 2013 11:57 darkness wrote:
This is a tricky question, but I guess because '2' is (sort of) considered as a variable. You change it to "10", you have do_stuff() 10 times. On the other hand, you can't change just 1 variable/number/thing in bar() to have do_stuff() executed more than twice.

The confusion may be about if you agree to imagine "2" as a variable instead of a number.

No, this is not how it works. Algorithmically, foo() and bar() are exactly the same thing which means they have the same complexity.

You don't randomly consider hardcoded things as variables. There would be infinitely many possible interpretations (2 = f(2) aka O(N), 2 = f(4) aka O(sqrt(N)) and so on). And code isn't considered changeable in the first place.
If you have a good reason to disagree with the above, please tell me. Thank you.
gedatsu
Profile Joined December 2011
1286 Posts
Last Edited: 2013-08-12 08:14:36
August 12 2013 08:11 GMT
#6812
Darkness, 2 is not a variable because it cannot vary at runtime. It is very much a constant., and hence the code runs in constant time. The fact that you can edit the code is entirely irrelevant, and also doesn't make any sense because you can always edit the code and therefore there wouldn't exist such a thing as constant time.
Tobberoth
Profile Joined August 2010
Sweden6375 Posts
August 12 2013 09:14 GMT
#6813
On August 12 2013 11:26 Morfildur wrote:
Show nested quote +
On August 12 2013 07:50 darkness wrote:
Most of us here have studied Computer Science or a branch of it, so you don't have to show off. You may also better your behaviour as one of the guys here has pointed out.

There is no confusion about Big O. Just because some guy writes crappy code with no variables doesn't mean we don't know Big O. If his code was better written, then it would have been O(n^2). Magic numbers are bad.


The confusion is:

void foo()
{
for (int i = 0; i < 2; ++i) do_stuff();
}

void bar()
{
do_stuff();
do_stuff();
}


Why should foo() be O(N) and bar() O(1) eventhough calling them always uses a constant amount of time since they do not change depending on their input?

Why would foo() be O(N)? I mean, if you simplify, you could say it's O(N) because it's one loop, but since the loop size is not dependent on input, it's just constant.
obesechicken13
Profile Blog Joined July 2008
United States10467 Posts
Last Edited: 2013-08-12 19:12:48
August 12 2013 13:46 GMT
#6814
O(1)
O(1) describes an algorithm that will always execute in the same time (or space) regardless of the size of the input data set.
bool IsFirstElementNull(String[] strings)
{
if(strings[0] == null)
{
return true;
}
return false;
}


Source:
http://rob-bell.net/2009/06/a-beginners-guide-to-big-o-notation/

Pretty sure some schools teach this differently. Can we put this to rest now?
I think in our modern age technology has evolved to become more addictive. The things that don't give us pleasure aren't used as much. Work was never meant to be fun, but doing it makes us happier in the long run.
HardlyNever
Profile Blog Joined July 2011
United States1258 Posts
August 12 2013 16:34 GMT
#6815
Anyone with a lot of experience with recaptcha? I got it to work on one of the forms I made, but I can't get it to work (it always fails, no matter what) on another form someone else made but I need to add it to. I've isolated the problem to an event handler javascript piece that for some reason always causes a fail. I'm not super familiar with javascript, especially if someone else wrote it (and this is kinda big), and was wondering if anyone has a similar problem in the past. Somewhere in here is the part that is causing the recaptcha to always fail (I'm thinking it is one of the set global variables, but I'm not sure). I believe it is some premade piece of script that a lot of people use. Warning, it is pretty big:

+ Show Spoiler +
/*******************************************************************************
* This notice must be untouched at all times.
*
* This javascript library contains helper routines to assist with event
* handling consinstently among browsers
*
* EventHelpers.js v.1.4 available at [url=http://www.useragentman.com/]http://www.useragentman.com/[/url]
*
* released under the MIT License:
* [url=http://www.opensource.org/licenses/mit-license.php]http://www.opensource.org/licenses/mit-license.php[/url]
*
* Chagelog: 1.4: fix fireEvent to work correctly for IE9.
*
*******************************************************************************/
var EventHelpers = new function(){
var me = this;

var safariTimer;
var isSafari = /WebKit/i.test(navigator.userAgent);
var globalEvent;

me.init = function () {
if (me.hasPageLoadHappened(arguments)) {
return;
}

/* This is for fireEvent */
if (document.createEvent) {
globalEvent = document.createEvent("HTMLEvents");
} else if (document.createEventObject){
// dispatch for IE8 and lower.
globalEvent = document.createEventObject();
}

me.docIsLoaded = true;
}

/**
* Adds an event to the document. Examples of usage:
* me.addEvent(window, "load", myFunction);
* me.addEvent(docunent, "keydown", keyPressedFunc);
* me.addEvent(document, "keyup", keyPressFunc);
*
* @author Scott Andrew - [url=http://www.scottandrew.com/weblog/articles/cbs-events]http://www.scottandrew.com/weblog/articles/cbs-events[/url]
* @author John Resig - [url=http://ejohn.org/projects/flexible-javascript-events/]http://ejohn.org/projects/flexible-javascript-events/[/url]
* @param {Object} obj - a javascript object.
* @param {String} evType - an event to attach to the object.
* @param {Function} fn - the function that is attached to the event.
*/
me.addEvent = function(obj, evType, fn){

if (obj.addEventListener) {
obj.addEventListener(evType, fn, false);
} else if (obj.attachEvent) {
obj['e' + evType + fn] = fn;
obj[evType + fn] = function(){
obj["e" + evType + fn](self.event);
}
obj.attachEvent("on" + evType, obj[evType + fn]);
}
}


/**
* Removes an event that is attached to a javascript object.
*
* @author Scott Andrew - [url=http://www.scottandrew.com/weblog/articles/cbs-events]http://www.scottandrew.com/weblog/articles/cbs-events[/url]
* @author John Resig - [url=http://ejohn.org/projects/flexible-javascript-events/]http://ejohn.org/projects/flexible-javascript-events/[/url] * @param {Object} obj - a javascript object.
* @param {String} evType - an event attached to the object.
* @param {Function} fn - the function that is called when the event fires.
*/
me.removeEvent = function(obj, evType, fn){

if (obj.removeEventListener) {
obj.removeEventListener(evType, fn, false);
} else if (obj.detachEvent) {
try {
obj.detachEvent("on" + evType, obj[evType + fn]);
obj[evType + fn] = null;
obj["e" + evType + fn] = null;
}
catch (ex) {
// do nothing;
}
}
}

function removeEventAttribute(obj, beginName){
var attributes = obj.attributes;
for (var i = 0; i < attributes.length; i++) {
var attribute = attributes[i]
var name = attribute.name
if (name.indexOf(beginName) == 0) {
//obj.removeAttributeNode(attribute);
attribute.specified = false;
}
}
}

me.addScrollWheelEvent = function(obj, fn){
if (obj.addEventListener) {
/** DOMMouseScroll is for mozilla. */
obj.addEventListener('DOMMouseScroll', fn, true);
}

/** IE/Opera. */
if (obj.attachEvent) {
obj.attachEvent("onmousewheel", fn);
}

}

me.removeScrollWheelEvent = function(obj, fn){
if (obj.removeEventListener) {
/** DOMMouseScroll is for mozilla. */
obj.removeEventListener('DOMMouseScroll', fn, true);
}

/** IE/Opera. */
if (obj.detachEvent) {
obj.detatchEvent("onmousewheel", fn);
}

}

me.getMouseCoords = function (e) {
if (!e) {
return;
}
// IE
if (e.clientX != null) {
return {
x: e.clientX,
y: e.clientY
}

}
// NS4
else if (e.pageX != null) {
return {
x: e.pageX,
y: e.pageY
}
// W3C
} else if (window.event != null && window.event.clientX != null
&& document.body != null &&
document.body.scrollLeft != null) {
return {
x: window.event.clientX + document.body.scrollLeft,
y: window.event.clientY + document.body.scrollTop
}

} else {
return null;
}
}

/**
* Given a mouse event, get the mouse pointer's x-coordinate.
*
* @param {Object} e - a DOM Event object.
* @return {int} - the mouse pointer's x-coordinate.
*/
me.getMouseX = function(e){
if (!e) {
return;
}
// NS4
if (e.pageX != null) {
return e.pageX;
// IE
} else if (window.event != null && window.event.clientX != null &&
document.body != null &&
document.body.scrollLeft != null)
return window.event.clientX + document.body.scrollLeft;
// W3C
else if (e.clientX != null)
return e.clientX;
else
return null;
}

/**
* Given a mouse event, get the mouse pointer's y-coordinate.
* @param {Object} e - a DOM Event Object.
* @return {int} - the mouse pointer's y-coordinate.
*/
me.getMouseY = function(e){
// NS4
if (e.pageY != null)
return e.pageY;
// IE
else if (window.event != null && window.event.clientY != null &&
document.body != null &&
document.body.scrollTop != null)
return window.event.clientY + document.body.scrollTop;
// W3C
else if (e.clientY != null) {
return e.clientY;
}
}
/**
* Given a mouse scroll wheel event, get the "delta" of how fast it moved.
* @param {Object} e - a DOM Event Object.
* @return {int} - the mouse wheel's delta. It is greater than 0, the
* scroll wheel was spun upwards; if less than 0, downwards.
*/
me.getScrollWheelDelta = function(e){
var delta = 0;
if (!e) /* For IE. */
e = window.event;
if (e.wheelDelta) { /* IE/Opera. */
delta = e.wheelDelta / 120;
/** In Opera 9, delta differs in sign as compared to IE.
*/
if (window.opera) {
delta = -delta;
}
} else if (e.detail) { /** Mozilla case. */
/** In Mozilla, sign of delta is different than in IE.
* Also, delta is multiple of 3.
*/
delta = -e.detail / 3;
}
return delta
}

/**
* Sets a mouse move event of a document.
*
* @deprecated - use only if compatibility with IE4 and NS4 is necessary. Otherwise, just
* use EventHelpers.addEvent(window, 'mousemove', func) instead. Cannot be used to add
* multiple mouse move event handlers.
*
* @param {Function} func - the function that you want a mouse event to fire.
*/
me.addMouseEvent = function(func){

if (document.captureEvents) {
document.captureEvents(Event.MOUSEMOVE);
}

document.onmousemove = func;
window.onmousemove = func;
window.onmouseover = func;

}



/**
* Find the HTML object that fired an Event.
*
* @param {Object} e - an HTML object
* @return {Object} - the HTML object that fired the event.
*/
me.getEventTarget = function(e){
// first, IE method for mouse events(also supported by Safari and Opera)
if (e.toElement) {
return e.toElement;
// W3C
} else if (e.currentTarget) {
return e.currentTarget;

// MS way
} else if (e.srcElement) {
return e.srcElement;
} else {
return null;
}
}




/**
* Given an event fired by the keyboard, find the key associated with that event.
*
* @param {Object} e - an event object.
* @return {String} - the ASCII character code representing the key associated with the event.
*/
me.getKey = function(e){
if (e.keyCode) {
return e.keyCode;
} else if (e.event && e.event.keyCode) {
return window.event.keyCode;
} else if (e.which) {
return e.which;
}
}


/**
* Will execute a function when the page's DOM has fully loaded (and before all attached images, iframes,
* etc., are).
*
* Usage:
*
* EventHelpers.addPageLoadEvent('init');
*
* where the function init() has this code at the beginning:
*
* function init() {
*
* if (EventHelpers.hasPageLoadHappened(arguments)) return;
*
* // rest of code
* ....
* }
*
* @author This code is based off of code from [url=http://dean.edwards.name/weblog/2005/09/busted/]http://dean.edwards.name/weblog/2005/09/busted/[/url] by Dean
* Edwards, with a modification by me.
*
* @param {String} funcName - a string containing the function to be called.
*/
me.addPageLoadEvent = function(funcName){

var func = eval(funcName);

// for Internet Explorer (using conditional comments)
/*@cc_on @*/
/*@if (@_win32)
pageLoadEventArray.push(func);
return;
/*@end @*/
if (isSafari) { // sniff
pageLoadEventArray.push(func);

if (!safariTimer) {

safariTimer = setInterval(function(){
if (/loaded|complete/.test(document.readyState)) {
clearInterval(safariTimer);

/*
* call the onload handler
* func();
*/
me.runPageLoadEvents();
return;
}
set = true;
}, 10);
}
/* for Mozilla */
} else if (document.addEventListener) {
var x = document.addEventListener("DOMContentLoaded", func, null);

/* Others */
} else {
me.addEvent(window, 'load', func);
}
}

var pageLoadEventArray = new Array();

me.runPageLoadEvents = function(e){
if (isSafari || e.srcElement.readyState == "complete") {

for (var i = 0; i < pageLoadEventArray.length; i++) {
pageLoadEventArray[i]();
}
}
}
/**
* Determines if either addPageLoadEvent('funcName') or addEvent(window, 'load', funcName)
* has been executed.
*
* @see addPageLoadEvent
* @param {Function} funcArgs - the arguments of the containing. function
*/
me.hasPageLoadHappened = function(funcArgs){
// If the function already been called, return true;
if (funcArgs.callee.done)
return true;

// flag this function so we don't do the same thing twice
funcArgs.callee.done = true;
}



/**
* Used in an event method/function to indicate that the default behaviour of the event
* should *not* happen.
*
* @param {Object} e - an event object.
* @return {Boolean} - always false
*/
me.preventDefault = function(e){

if (e.preventDefault) {
e.preventDefault();
}

try {
e.returnValue = false;
}
catch (ex) {
// do nothing
}

}

me.cancelBubble = function(e){
if (e.stopPropagation) {
e.stopPropagation();
}

try {
e.cancelBubble = true;
}
catch (ex) {
// do nothing
}
}

/*
* Fires an event manually.
* @author Scott Andrew - [url=http://www.scottandrew.com/weblog/articles/cbs-events]http://www.scottandrew.com/weblog/articles/cbs-events[/url]
* @author John Resig - [url=http://ejohn.org/projects/flexible-javascript-events/]http://ejohn.org/projects/flexible-javascript-events/[/url]
* @param {Object} obj - a javascript object.
* @param {String} evType - an event attached to the object.
* @param {Function} fn - the function that is called when the event fires.
*
*/
me.fireEvent = function (element,event, options){

if(!element) {
return;
}

if (element.dispatchEvent) {
// dispatch for firefox + ie9 + others
globalEvent.initEvent(event, true, true); // event type,bubbling,cancelable
return !element.dispatchEvent(globalEvent);
} else if (document.createEventObject){
return element.fireEvent('on' + event, globalEvent)
} else {
return false;
}
}

/*
* Detects whether the event "eventName" is supported on a tag with name
* "nodeName". Based on code from
* [url=http://perfectionkills.com/detecting-event-support-without-browser-sniffing/]http://perfectionkills.com/detecting-event-support-without-browser-sniffing/[/url]
*/
me.isSupported = function (eventName, nodeName) {
var el = document.createElement(nodeName);
eventName = 'on' + eventName;
var isSupported = (eventName in el);
if (!isSupported) {
el.setAttribute(eventName, 'return;');
isSupported = typeof el[eventName] == 'function';
}
el = null;
return isSupported;
}


/* EventHelpers.init () */
function init(){
// Conditional comment alert: Do not remove comments. Leave intact.
// The detection if the page is secure or not is important. If
// this logic is removed, Internet Explorer will give security
// alerts.
/*@cc_on @*/
/*@if (@_win32)

document.write('<script id="__ie_onload" defer src="' +

((location.protocol == 'https:') ? '//0' : 'javascript:void(0)') + '"><\/script>');

var script = document.getElementById("__ie_onload");

me.addEvent(script, 'readystatechange', me.runPageLoadEvents);

/*@end @*/

}

init();
}

EventHelpers.addPageLoadEvent('EventHelpers.init');


I can't just remove the event helper, as this particular form needs it to do what it needs to do right. I may be able to come up with a simpler solution for getting the form to work if I can't figure it out. I don't 100% need recaptcha on this form, but it would be nice as we've had a few spam bots hit it.
Out there, the Kid learned to fend for himself. Learned to build. Learned to break.
heroyi
Profile Blog Joined March 2009
United States1064 Posts
Last Edited: 2013-08-13 04:59:24
August 13 2013 04:32 GMT
#6816
wat wat in my pants
Encdalf
Profile Joined February 2012
Germany66 Posts
August 13 2013 07:46 GMT
#6817
On August 13 2013 01:34 HardlyNever wrote:
Anyone with a lot of experience with recaptcha? I got it to work on one of the forms I made, but I can't get it to work (it always fails, no matter what) on another form someone else made but I need to add it to. I've isolated the problem to an event handler javascript piece that for some reason always causes a fail. I'm not super familiar with javascript, especially if someone else wrote it (and this is kinda big), and was wondering if anyone has a similar problem in the past. Somewhere in here is the part that is causing the recaptcha to always fail (I'm thinking it is one of the set global variables, but I'm not sure). I believe it is some premade piece of script that a lot of people use. Warning, it is pretty big:

[...]

I can't just remove the event helper, as this particular form needs it to do what it needs to do right. I may be able to come up with a simpler solution for getting the form to work if I can't figure it out. I don't 100% need recaptcha on this form, but it would be nice as we've had a few spam bots hit it.


I'm sorry, but without any further context, I doubt anyone will be able to help you. This is a problem caused by the combination of scripts on your page, and without a live example these things are pretty hard to track down.

Or to put it into a metaphor..
You get a combustion engine to a mechanic, and tell him "I think this eingine is broken.". "Why?" the mechanic asks. "Well, I checked everything and I believe it's the engine which is broken.". The mechanic checks the engine, but unfortunately the engine is brand new and working perfectly.
The real problem was somewhere else: The car was electric.
Shield
Profile Blog Joined August 2009
Bulgaria4824 Posts
Last Edited: 2013-08-13 08:24:58
August 13 2013 08:19 GMT
#6818
Where do you guys read/learn which algorithm is best for your problem? For example, I've read today that MergeSort is best for linked lists, while QuickSort is best for general use and that it is more memory efficient than MergeSort. Well, I guess that's logical when you know MergeSort uses additional array.

Is it also a good idea to just use already implemented algorithms in the language you use? I've read that std::sort, Java's Collections.sort(), Linked List, etc are much more optimised than you would possibly implement them.
Tobberoth
Profile Joined August 2010
Sweden6375 Posts
August 13 2013 08:30 GMT
#6819
On August 13 2013 17:19 darkness wrote:
Where do you guys read/learn which algorithm is best for your problem? For example, I've read today that MergeSort is best for linked lists, while QuickSort is best for general use and that it is more memory efficient than MergeSort. Well, I guess that's logical when you know MergeSort uses additional array.

Is it also a good idea to just use already implemented algorithms in the language you use? I've read that std::sort, Java's Collections.sort(), Linked List, etc are much more optimised than you would possibly implement them.

You pretty much just have to learn various algorithms to know in what cases they are strong/weak. If you're sorting a huge list of heavy objects, you probably want something memory efficient, while if it's several smaller lists you might want something faster.

I think best practice is to use library functions almost always nowadays, unless you specifically know that the language implementation is suboptimal for your problem at hand. It makes you far more productive and the designers of the language know what they are doing and specifically implement their algorithms to be good for the most common situations.

It's also worth noting that optimization on the level of which algorithm to use often has a very small impact unless you're talking heavy calculations. Which sort you use for a few hundred string entries will probably not impact your performance noticeably.
spinesheath
Profile Blog Joined June 2009
Germany8679 Posts
August 13 2013 08:37 GMT
#6820
On August 13 2013 17:19 darkness wrote:
Where do you guys read/learn which algorithm is best for your problem? For example, I've read today that MergeSort is best for linked lists, while QuickSort is best for general use and that it is more memory efficient than MergeSort. Well, I guess that's logical when you know MergeSort uses additional array.

Is it also a good idea to just use already implemented algorithms in the language you use? I've read that std::sort, Java's Collections.sort(), Linked List, etc are much more optimised than you would possibly implement them.

Yes, you always should use existing implementations by default. Especially if they come with the language or standard librariers. Only if you have very special requirements that existing algorithms can't fulfill you should look for a specialized implementation.

You should almost never have to implement a sorting algorithm by hand. The fact that the existing implementations usually are more robust and faster than your own implementations doesn't even matter. It's mostly about saving coding and debugging time. Your code will be buggy at first no matter what, while existing code has been tested thoroughly.
If you have a good reason to disagree with the above, please tell me. Thank you.
Prev 1 339 340 341 342 343 1031 Next
Please log in or register to reply.
Live Events Refresh
SC Evo League
12:00
S2 Championship: Ro16 Day 2
SteadfastSC82
EnkiAlexander 33
IntoTheiNu 10
Liquipedia
WardiTV Summer Champion…
11:00
Playoffs Day 1
ByuN vs herO
MaxPax vs Zoun
Clem vs NightMare
WardiTV1132
Liquipedia
Sparkling Tuna Cup
10:00
Weekly #103
Solar vs ShoWTimELIVE!
ByuN vs TBD
CranKy Ducklings332
LiquipediaDiscussion
[ Submit Event ]
Live Streams
Refresh
StarCraft 2
Rex 137
BRAT_OK 103
ProTech92
SteadfastSC 82
StarCraft: Brood War
Britney 43288
Larva 906
Killer 393
Hyun 324
Hyuk 295
Last 289
Mini 283
Rush 263
Pusan 252
ggaemo 240
[ Show more ]
firebathero 198
PianO 191
Mind 131
soO 33
Free 23
ajuk12(nOOB) 19
HiyA 15
Noble 10
Sacsri 9
Dota 2
Gorgc10465
qojqva1552
XcaliburYe325
Pyrionflax220
Fuzer 148
League of Legends
Dendi778
Counter-Strike
summit1g9144
olofmeister1836
Super Smash Bros
Mew2King60
Heroes of the Storm
Khaldor211
Other Games
singsing2002
B2W.Neo1111
byalli216
RotterdaM180
KnowMe51
rGuardiaN17
Organizations
StarCraft 2
Blizzard YouTube
StarCraft: Brood War
BSLTrovo
sctven
[ Show 15 non-featured ]
StarCraft 2
• Reevou 10
• intothetv
• AfreecaTV YouTube
• Kozan
• IndyKCrew
• LaughNgamezSOOP
• Migwel
• sooper7s
StarCraft: Brood War
• BSLYoutube
• STPLYoutube
• ZZZeroYoutube
Dota 2
• C_a_k_e 2849
• WagamamaTV444
League of Legends
• Nemesis4457
• Jankos2595
Upcoming Events
Chat StarLeague
2h 38m
Razz vs Julia
StRyKeR vs ZZZero
Semih vs TBD
Replay Cast
10h 38m
Afreeca Starleague
20h 38m
Queen vs HyuN
EffOrt vs Calm
Wardi Open
21h 38m
RotterdaM Event
1d 1h
Replay Cast
1d 10h
Afreeca Starleague
1d 20h
Rush vs TBD
Jaedong vs Mong
WardiTV Summer Champion…
1d 21h
PiGosaur Monday
2 days
Afreeca Starleague
2 days
herO vs TBD
Royal vs Barracks
[ Show More ]
Replay Cast
3 days
The PondCast
3 days
WardiTV Summer Champion…
3 days
Replay Cast
4 days
LiuLi Cup
4 days
Cosmonarchy
5 days
OyAji vs Sziky
Sziky vs WolFix
WolFix vs OyAji
BSL Team Wars
5 days
Team Hawk vs Team Dewalt
BSL Team Wars
5 days
Team Hawk vs Team Bonyth
SC Evo League
5 days
[BSL 2025] Weekly
6 days
SC Evo League
6 days
Liquipedia Results

Completed

Jiahua Invitational
uThermal 2v2 Main Event
HCC Europe

Ongoing

Copa Latinoamericana 4
BSL 20 Team Wars
KCM Race Survival 2025 Season 3
BSL 21 Qualifiers
ASL Season 20
CSL Season 18: Qualifier 1
Acropolis #4 - TS1
CSLAN 3
SEL Season 2 Championship
WardiTV Summer 2025
Esports World Cup 2025
BLAST Bounty Fall 2025
BLAST Bounty Fall Qual
IEM Cologne 2025
FISSURE Playground #1
BLAST.tv Austin Major 2025

Upcoming

CSL Season 18: Qualifier 2
CSL 2025 AUTUMN (S18)
LASL Season 20
BSL Season 21
BSL 21 Team A
Chzzk MurlocKing SC1 vs SC2 Cup #2
RSL Revival: Season 2
Maestros of the Game
EC S1
Sisters' Call Cup
IEM Chengdu 2025
PGL Masters Bucharest 2025
MESA Nomadic Masters Fall
Thunderpick World Champ.
CS Asia Championships 2025
Roobet Cup 2025
ESL Pro League S22
StarSeries Fall 2025
FISSURE Playground #2
BLAST Open Fall 2025
BLAST Open Fall Qual
TLPD

1. ByuN
2. TY
3. Dark
4. Solar
5. Stats
6. Nerchio
7. sOs
8. soO
9. INnoVation
10. Elazer
1. Rain
2. Flash
3. EffOrt
4. Last
5. Bisu
6. Soulkey
7. Mini
8. Sharp
Sidebar Settings...

Advertising | Privacy Policy | Terms Of Use | Contact Us

Original banner artwork: Jim Warren
The contents of this webpage are copyright © 2025 TLnet. All Rights Reserved.