4 ms·

That's the point, there is no magic library that can do this for you. For example, let's say you're writing Python and have a list of receipt numbers. When you

That's the point, there is no magic library that can do this for you. For example, let's say you're writing Python and have a list of receipt numbers. When you get a new receipt, you want to check if it's already in the list, so you do the pythonic thing: "if receipt_nr in receipts", assuming that the standard implementation of this operation in the library is efficient. The problem is, a set would be a lot more efficient here, but the standard library doesn't know you'll be checking if a number is in the list many times, so it cannot use the appropriate data structure. So, in a way, the time and space complexity of each operation is part of the interface: maybe you don't really need to know how the internals are implemented, but at the very least you need to know the time and space complexity of the data structures you're using, and how to analyse the complexity of your code.

riskable 10y ago
What's funny about your example is that using a set in that situation would be an example of premature optimization. If your entire list of receipts fits into memory users won't notice a difference between a list and a set. Also, if you used a list in Python (or other similar dynamic languages) swapping a list out for a set is a trivial operation... receipts = [] # ...becomes: receipts = set() ...and it would require no changes to the conditional logic of the application. So later, if it turns out you're having performance issues you (usually) make a few minor changes here and there and get your 10x or 100x or even 10,000x speedup.
- kchoudhu 10y ago
  Not to mention that most of the kids today would have stowed their entire population of receipts in whatever the datastore flavor-of-the-week is. At that point, the lookup would effectively be a SELECT -- which the DBMS would optimize away for you.
  - pjc50 10y ago
    .. unless they've forgotten the index, at which point the DBMS grinds to a halt. Or they've written the query on the wrong side of the ORM so it has to pull in all the objects, check the value, and discard them.
  - emodendroket 10y ago
    A very simple example that I think is "real-world" enough is recursively descending the fields of some object which has cycles. If you use a list instead of a set this can be quite slow.
- scott_s 10y ago
  > If your entire list of receipts fits into memory users won't notice a difference between a list and a set. If you had said "small enough", I would agree, but linear walks of data that can fit in memory can easily be noticed by users, for large enough lists. (Very large lists can fit in memory.) But, at a higher level, yes, this is always true when people talk about performance: make sure what you're optimizing actually matters. I think a charitable reading of what ThePawnBreak said should assume one has already determined this particular operation matters for performance.
  - pjc50 10y ago
    Earlier this month I was looking at the question of "why does it take 160ms to scan a list of just 60,000 items? The answer turned out to be "because they're not adjacent and on this embedded system every single cache miss costs you hundreds of nanoseconds". I strongly agree that, like woodworkers, performance improvers should measure before they take out the power tools.
- emodendroket 10y ago
  > What's funny about your example is that using a set in that situation would be an example of premature optimization. If your entire list of receipts fits into memory users won't notice a difference between a list and a set. That's completely untrue if you're running this check often enough.
- deleted 10y ago
  [deleted]
kchoudhu 10y ago
Next question: how often would this kind of malprogramming actually lead to deal-breaking performance issues in a project? After a decade in the industry, countless projects delivered and much shit code witnessed, I can empirically answer this question, and the the answer is -- even at places that are known for their technical excellence -- not often. Look, I'm not advocating illiterate programming, nor am I a proponent of unprofessional work. I took my share of CS classes, and I can talk about algorithms and how to analyze them. The number of times I have had to do so on the job, however, can be counted on my bodily digits, without taking off my shoes. This is probably not an original observation, but a big part of why these unproductive conversations keep on happening here has to do with how young HN demographic skews. When the biggest achievement in your life is getting that new degree you spent $BIGNUMBER $$/years on, you're going to want to belittle workmanlike programmers who don't measure up to your own standards. It takes a while for people to move on and grow up.
- pjc50 10y ago
  > how often would this kind of malprogramming actually lead to deal-breaking performance issues in a project? Depends very much on your projects. Web developers generally have it easy, as it's cheap to add more servers and free to burn CPU in the browser. Even so you can get into trouble with anything that's O(N) in the number of users. I do wonder how much use of nosql is from people who think SQL is slow because they've not got their indexes set up properly. Game developers, of course, live and breathe performance. As do embedded and similar low-level environments. Or people working with this trendy "big" data.
- sbov 10y ago
  Performance will rarely be deal breaking. Instead people will toil away with slow systems and just accept it. It doesn't mean that they wouldn't be much happier with a faster system. We recently replaced a system whose online store took about 900ms to respond, and their back end admin section on average around 1.7 seconds. It obviously wasn't deal breaking since they lived with it for 3 years but it still was still ridiculous, and definitely had an impact on both their productivity and bottom line.
- emodendroket 10y ago

riskable 10y ago

What's funny about your example is that using a set in that situation would be an example of premature optimization. If your entire list of receipts fits into memory users won't notice a difference between a list and a set. Also, if you used a list in Python (or other similar dynamic languages) swapping a list out for a set is a trivial operation... receipts = [] # ...becomes: receipts = set() ...and it would require no changes to the conditional logic of the application. So later, if it turns out you're having performance issues you (usually) make a few minor changes here and there and get your 10x or 100x or even 10,000x speedup.

kchoudhu 10y ago
Not to mention that most of the kids today would have stowed their entire population of receipts in whatever the datastore flavor-of-the-week is. At that point, the lookup would effectively be a SELECT -- which the DBMS would optimize away for you.
- pjc50 10y ago
  .. unless they've forgotten the index, at which point the DBMS grinds to a halt. Or they've written the query on the wrong side of the ORM so it has to pull in all the objects, check the value, and discard them.
- emodendroket 10y ago
  A very simple example that I think is "real-world" enough is recursively descending the fields of some object which has cycles. If you use a list instead of a set this can be quite slow.
scott_s 10y ago
> If your entire list of receipts fits into memory users won't notice a difference between a list and a set. If you had said "small enough", I would agree, but linear walks of data that can fit in memory can easily be noticed by users, for large enough lists. (Very large lists can fit in memory.) But, at a higher level, yes, this is always true when people talk about performance: make sure what you're optimizing actually matters. I think a charitable reading of what ThePawnBreak said should assume one has already determined this particular operation matters for performance.
- pjc50 10y ago
  Earlier this month I was looking at the question of "why does it take 160ms to scan a list of just 60,000 items? The answer turned out to be "because they're not adjacent and on this embedded system every single cache miss costs you hundreds of nanoseconds". I strongly agree that, like woodworkers, performance improvers should measure before they take out the power tools.
emodendroket 10y ago
> What's funny about your example is that using a set in that situation would be an example of premature optimization. If your entire list of receipts fits into memory users won't notice a difference between a list and a set. That's completely untrue if you're running this check often enough.
deleted 10y ago
[deleted]

kchoudhu 10y ago

Next question: how often would this kind of malprogramming actually lead to deal-breaking performance issues in a project? After a decade in the industry, countless projects delivered and much shit code witnessed, I can empirically answer this question, and the the answer is -- even at places that are known for their technical excellence -- not often. Look, I'm not advocating illiterate programming, nor am I a proponent of unprofessional work. I took my share of CS classes, and I can talk about algorithms and how to analyze them. The number of times I have had to do so on the job, however, can be counted on my bodily digits, without taking off my shoes. This is probably not an original observation, but a big part of why these unproductive conversations keep on happening here has to do with how young HN demographic skews. When the biggest achievement in your life is getting that new degree you spent $BIGNUMBER $$/years on, you're going to want to belittle workmanlike programmers who don't measure up to your own standards. It takes a while for people to move on and grow up.

pjc50 10y ago
> how often would this kind of malprogramming actually lead to deal-breaking performance issues in a project? Depends very much on your projects. Web developers generally have it easy, as it's cheap to add more servers and free to burn CPU in the browser. Even so you can get into trouble with anything that's O(N) in the number of users. I do wonder how much use of nosql is from people who think SQL is slow because they've not got their indexes set up properly. Game developers, of course, live and breathe performance. As do embedded and similar low-level environments. Or people working with this trendy "big" data.
sbov 10y ago
Performance will rarely be deal breaking. Instead people will toil away with slow systems and just accept it. It doesn't mean that they wouldn't be much happier with a faster system. We recently replaced a system whose online store took about 900ms to respond, and their back end admin section on average around 1.7 seconds. It obviously wasn't deal breaking since they lived with it for 3 years but it still was still ridiculous, and definitely had an impact on both their productivity and bottom line.
emodendroket 10y ago