I did a few efficiency tests recently to see what was the best choice when faced with multiple ways to accomplish the same action.
Can anyone think of any other situations where you could use one option over another and what the result would be?
Here are my tests/results:
X in List Vs. List.Find(X)
Results: List.Find(X) is considerably faster
List Association, Two Separate Lists, One Multi Dimensional List
Results: Associative lists were clearly the slowest. What seemed odd was most of the time the multi-dimensional list and dual lists tied, but occasionally the multi-dimensional list would be faster by a short amount of time (usually no more than a tick)
ID:151706
 Jul 31 2009, 3:46 pm
|
|
Foomer wrote:
AJX wrote: I was actually surprised by that, because I've always been told I should use X in List. :S | |
AJX wrote:
Foomer wrote: Likewise, and I'd been using it a lot lately. What about list += item vs list.Add(item) and other list functions? | |
Foomer wrote:
What about list += item vs list.Add(item) and other list functions? Beginning Test: List Data Adding Test. Amount: 20000 (Stage 1: List[++Len]=Data) Operation took 0.3 seconds Beginning Test: List Data Adding Test. Amount: 20000 (Stage 1.5: Len++, List[i]=Data) Operation took 0.7 seconds Beginning Test: List Data Adding Test. Amount: 20000 (Stage 2: List += Data) Operation took 0.6 seconds Beginning Test: List Data Adding Test. Amount: 20000 (Stage 3: List.Add(Data)) Operation took 0.6 seconds I threw in Stage 1.5 to make sure there was a difference between len++ and list[++len]=data And there very clearly was. List[++len]=data is the clear winner. In case anyone wanted to see, here is the source for the tests I ran. http://www.byond.com/developer/AJX/EfficiencyTests **EDIT*: This is odd... If you repeat the tests they give varying results. I haven't seen any where the speed results weren't accurate, but there have been a few where all 4 of them tied... :S I'm experimenting with this further to try and figure it out. **EDIT AGAIN: Well.. it appears that the inconsistancy is caused from repeating the tests in the same dream seeker, instead of starting a new one. Not sure why this is... I set the list len to 0 before each segment of the test, and gave a delay in between to make sure that wasn't causing the problem. Huh. Weird. | |
You mucked up your test by reusing the same list, but the results are interesting anyway: all methods are of equal efficiency, but whichever one goes first is by far the fastest.
Interestingly, if a new list is created for each of them each time... the first one seems to end up going the slowest after the first call. | |
Garthor wrote:
You mucked up your test by reusing the same list, but the results are interesting anyway: all methods are of equal efficiency, but whichever one goes first is by far the fastest. EDIT: Well I retested everything. I did the tests with 60k values, I did them one after another, sequentially, repeated them... They all ranged between 0.7-0.9, and there appeared to be no clear superior or inferior way of doing it. Curse you Garthor for being right! :( | |
The difference in efficiency is a result of the order you're calling them in. There appears to be some overhead when lists are to be reused, and it only applies to the first use of the lists in the proc, for whatever reason. If you add sleep(100000) to the end of it, the lists aren't freed (you can verify by printing out the \ref which gives the memory location) and subsequent calls all go quickly.
| |
Garthor wrote:
The difference in efficiency is a result of the order you're calling them in. There appears to be some overhead when lists are to be reused, and it only applies to the first use of the lists in the proc, for whatever reason. If you add sleep(100000) to the end of it, the lists aren't freed (you can verify by printing out the \ref which gives the memory location) and subsequent calls all go quickly. Read my edit in the post you're replying to. Summary: CURSE YOU! :( Real Summary: Yea... yur right. <_< >_> Good news though, I retested the X in List and List.Find(X) results, and they are still conclusive. I haven't tried the lists ones again yet, but they are held in separate lists so I can't imagine that it would have an effect. | |
AJX wrote:
Good news though, I retested the X in List and List.Find(X) results, and they are still conclusive. I had no doubt of that given that my current project works 4 times faster using Find(). | |
Foomer wrote:
AJX wrote: Good news. Glad to have been of assistance. :D | |
Just chiming in to point out something that was seemingly missed: in and Find() do not really perform the same action (and I'm not referring to the different return value*), so you're comparing 2 different things here. I think I've mentioned to you (AJX) before on this subject that 'in' is more robust, since you can use it on a var that may not actually contain a list with no issue. This is because it includes a type check. Find(), being the proc it is, doesn't, as that would be pointless (normally, if you'd use it on a non-list, the proc won't even be called, you'd just get an error). So it's kind of common sense that 'in' is slower - it does more. To compare it equally with Find(), you'd have to include a type check in the process, which is going to be inevitably slower since with 'in' it's automatically done internally. So if in a given scenario you'd want to include a list type-check, 'in' would actually be the faster method to use.
*: When thinking about that, it would really have been better (from a general-usefulness standpoint) for 'in' to have the same return value as Find()... | |
Kaioken wrote:
... Yea. you had mentioned that before, and now that I think about it, it makes sense that Find() is more efficient. The PROBLEM is that most people (and Foomer said even the reference itself) encourages the use of X In List, which is considerably more inefficient. | |
It's not really "considerably" more efficient, it's barely more efficient, to the point where it's more of a preference (of course, in is much more useful, still, which is why I prefer to use it).
| |
And why exactly is that a "PROBLEM"? As we've just discussed, 'in' is more robust - and it's not slow*. Then why not encourage using it?
Besides, your concept of 'efficiency' here is flawed. You're comparing efficiency here based on raw execution speed alone, not on what each instruction actually does. Efficiency is about more than just execution speed. *: In case you don't follow this part, it's not slow objectively, not compared to Find(), and in fact, as previously mentioned, using it is faster than reproducing the same robustness using Find(). | |
Jeff8500 wrote:
It's not really "considerably" more efficient, it's barely more efficient, to the point where it's more of a preference (of course, in is much more useful, still, which is why I prefer to use it). I don't know what kinda tests you were doing, but as Foomer said when he replaced his In's with Find's his code operated four times faster. On the tests I ran the speed difference was pretty large, well over double. That qualifies as 'considerably' to me. | |
Kaioken wrote:
> And why exactly is that a "PROBLEM"? As we've just discussed, 'in' is more robust - and it's not slow*. Then why not encourage using it? What we're discussing here is a matter of opinion, except for ONE thing: When considered in reference to finding if something is in a list or not, List.Find() is WITHOUT QUESTION the faster choice. That being the case, whether it is a problem or not to be encouraging the use of 'in' in that situation is opinion. I think that In should be encouraged in situations where its robustness is necessary, but it should be made clear that Find() is the better choice for checking if something is in a list. However, this is my OPINION, and as such doesn't really matter. > Besides, your concept of 'efficiency' here is flawed. Efficiency is a very robust word, with many definitions. Your statement is flawed. My concept of efficiency is not the same as every definition of efficiency, and use are using a definition that fits your argument, though that is CLEARLY not the one I am using. > You're comparing efficiency here based on raw execution speed alone, not on what each instruction actually does. Efficiency is about more than just execution speed. Again, efficiency is a word with many definitions. You are smart enough to know which one I am referring to. In case anyone isn't clear on that, when I say 'efficiency', I'm referring to the dictionary definition: accomplishment of or ability to accomplish a job with a minimum expenditure of time and effort. In case you feel like playing with words on that definition, let me preemptively clarify once more: effort referring to the amount of power used to handle the computations on the part of the computer. > *: In case you don't follow this part, it's not slow objectively, not compared to Find(), and in fact, as previously mentioned, using it is faster than reproducing the same robustness using Find(). Sigh... It seems to me that people on BYOND's forums have the uncontrollable urge to argue for the sake of arguing. I don't mean that offensively, it just gets tiring at times. Allow me to clarify something: Common sense would dictate that when I speak of efficiency here, I am referring to the speed at which the program can execute the code in the specific context of what I'm using it for. Why would common sense dictate this fact? A quick analysis of my code shows that I am using it with the specific purpose of checking if something is in a list or not. The benchmarks that I am measuring the results in... What are they? Time. The fact is this: You may say "'in' is more robust, and it's not slow, then why not encourage using it?", but that statement is foolish. You should use whatever functionality is better for the situation you are using it in. That is again, common sense. It is important to teach new programmers to apply common sense while programming. Telling people that 'Oh, this proc can do more things so you should always use it' is very poor programming practice. Telling people 'This proc is very robust and can be used in situations where the other can not, but operates slower.' is not only THE TRUTH, but much more valuable information. | |
AJX wrote:
What we're discussing here is a matter of opinion, except for ONE thing: Apparently you haven't noticed, but we're not discussing that here. That has been long before established. This subthread started when you said that people advising to use 'in' is a problem, and that's its topic. The definition of efficiency rant was pretty pointless, really. I knew what you meant, and was using the same definition. The point was mainly that 'in' does something that Find() doesn't, and that makes it more efficient when it's needed. All depends on the situation. It is important to teach new programmers to apply common sense while programming. Sure, though it's not always plausible or productive to explain everything to someone who asks something. For example, if it's a newbie in question, you probably want to keep it simple, which may include not bombarding him with misc information of when to do this and when to do that which complicates the matter. Giving the solution which is a little less prone to fail and is easier to use and understand sounds like a fine compromise. Telling people that 'Oh, this proc can do more things so you should always use it' is very poor programming practice. For that matter, there's really virtually no harm in using 'in' "always". Programming more robustly is generally... definitely not a "very poor programming practice". At any case, something like a general suggestion to use 'in' doesn't do any harm. No one said anything about telling someone to strictly always use something under any circumstances or anything like that. Telling people 'This proc is very robust and can be used in situations where the other can not, but operates slower.' is not only THE TRUTH, but much more valuable information. Correct, but it's not a requirement. If someone asks "How do I check if a list contains and certain value?" and someone answers "You can use 'in'", it's not a bad answer. Maybe it's not a complete and full-fledged one, but how verbose and detailed to be is up to the specific helper in question, and also other factors such as the situation, the person being helped, the mood of the helper... =P | |
Good to know.