Rust-Cache | Hacker News Reader

Rust-Cache

crates.io

This crate was downloaded less than 100 times in total until yesterday. Today it has 74,797,449 downloads. Looks a bit sketchy

Interestingly it now down again to only 27 total downloads. Looks like the crates.io team cleaned it up. The search results page still shows millions of downloads. Let's hope that's just a cached number and gets taken care of too.

> Today it has 74,797,449 downloads.

Maybe one of the users forgot to cache their deps (:

It has 3 stars on github.

inb4 the project suddenly gets millions of stars on GitHub

> Now we can make an assumption that the int it's a finite number say u32, this means we can construct a binary tree with a depth of 32 with access time of O(32) therefore O(1) time and space.

Heck, let's go even further. All the computers I've used have a fixed amount of memory, addressable by a u64, so I guess all my algorithms are constant time now.

I guess we've solved the interview, folks.

big-O notation isn't some fundamental secret of the universe. It's a model devised by humans, and typically used in the context of real world computers as a means for conveying an understanding of how algorithms scale.

If we considered the bits of integers as the smallest unit of work in all cases (it is of course relevant to consider bits as the unit of work in some cases), then big-O notation becomes a lot more tedious without typically adding more value.

See: https://cs.stackexchange.com/questions/140642/silly-question...

Still it's a notation that had meaning, about the behavior as n goes to infinity. If you take out n, or if you don't have an n, just don't use it.

What? Saying something takes O(1) time or space is absolutely meaningful.

https://en.wikipedia.org/wiki/Big_O_notation#Orders_of_commo...

Setting n=1 to say your O(n) is actually O(1) makes no sense because big O notation tells us how the time/space grow as function of the input size. If n=1, input size is fixed.

That's not what is happening here. The n cannot grow because the representation is fixed.

Read the links I've provided. The convention and meaning are clear here.

O notation has meaning if something is 'n' and that 'n' can grow. Without an n defined somewhere, nothing can be O(n), nothing can be O(1).

I think the links I've provided sufficiently explain what the common convention is. And in the context in which the notation is used here, it is crystal clear what is meant.

This feels to me like errant niggling for the sake of it.

From your link (emphasis mine):

> In each case, c is a positive constant and *n increases without bound*

It is indeed crystal clear what "asymptotic" means. If you have a definition for O-notation in non-asymptotic contexts, I have never heard of it.

I no longer understand where your confusion is, so I'm not sure how to respond. I'd suggest taking it back to what was actually said in the OP and the criticism it got. Otherwise, if you're arriving in ridiculous places like "you must be trying to say that O-notation is used in non-asymptotic contexts," then there's very clearly some kind of miscommunication or misunderstanding. From my perspective, your comments are terse, unclear and not addressing the central point directly.

I try to explain with a practical example: Let's say I define a list with worst-case lookup time of O(n). Simplified this means that when I have a list of 100 elements and append 1 element, then the worst case lookup time increases from 100C to 101C where C is some constant time. The O(n) tells me how the runtime of the operation changes if I alter the input size.

Now the OP's idea is this: I'll fix the size of allowed elements in my list to some maximum value, lets say n=5, and then you always end up with the same worst-case time, O(1), because the input size is constant. With 5 elements it looks silly but you could say n = (very large number that won't be exceeded ever) and conclude that O(n=1). In OPs case the n is the number of bits in the key (implies a radix-tree)

=> If an algorithm is defined as being unscalable (fixed input), what sense does it make to describe that it scales constantly with input size?

I agree with everything you said, but I don't see how it leads the OP's formulation being silly or wrong or not useful. Here's another example (of my own) where you can pick an upper bound for `n` and base your complexity analysis around it. In this case, we're trying to provide an API guarantee that a search takes O(m+n) time despite wanting to use an O(mn) algorithm in some subset of cases. We can still meet the O(m+n) bound by reasoning that the O(mn) algorithm is only used in a finite set of cases, and thus collapses to O(1) time. Therefore, the O(m+n) time bound is preserved. And this isn't a trick either. That really is the scaling behavior of the implementation. See: https://github.com/BurntSushi/memchr/blob/ce7b8e606410f6c81a...

> If an algorithm is defined as being unscalable (fixed input), what sense does it make to describe that it scales constantly with input size?

I'll answer your question with another: in what cases does it make sense to describe the scaling behavior of an algorithm as O(1)?

Everybody else in this thread is getting it, while you are only leveling personal attacks at me with no arguments whatsoever. Terse, ridiculous, confused, errant niggling? Why is this the way you have to communicate?

I'm sorry for coming across harsh. I tried to stick to commentary about your words, not you as a person. That's why I said "your comments are." I legitimately find your commenting here rather frustrating. It feels to me like you're posting zingers instead of trying to come to a mutual understanding.

I'll try one last time. I personally feel like this answer[1] very clearly refutes the criticism leveled in the top-level comment[2]. Specifically, the opening parts of the answer:

> It depends on the computational model you choose. It is obviously not true that two numbers can be added together in constant time regardless of their size. If you think about it in terms of the most elementary operations, those on individual bits, adding two n-bit numbers would require O(n) elementary operations. And multiplying two n-bit numbers would use O(n2) elementary operations if you do it using long multiplication. You can easily try this out for yourself using pen and paper.

> The problem with this viewpoint is that it makes analyzing algorithms very tedious. Any time we would add two numbers a and b we would have to figure out that they would have loga and logb bits respectively and that the addition would take O(loga+logb) time. This would make the analysis much more tedious, and result in running time with lots of logs in them.

And thus, by convention, big-O notation typically uses an `n` that is defined in terms of units of bits and not just bits themselves. This is why it can make sense to declare something O(1) even when it might actually be O(logn) where n is the number of bits in the input.

[1]: https://cs.stackexchange.com/a/140646

[2]: https://news.ycombinator.com/item?id=38511259

> And thus, by convention, big-O notation typically uses an `n` that is defined in terms of units of bits and not just bits themselves. This is why it can make sense to declare something O(1) even when it might actually be O(logn) where n is the number of bits in the input.

I don't disagree with this at all, now the question is: what is n in the case we are talking about? That goes to infinity as we evaluate the cost of this cache system, allowing us to use *asymptotic O notation*?

Yeah, my curiously disappeared when I read this line.

The answer to this question is always use Redis or memcached. Nothing you whip up on your own is ever going to be a good as a well tested cache implementation that has seen every edge case.

This is the difference between a mid-level and a senior engineer during an interview. The latter will explain to you the pitfalls of what you are asking for before even considering writing a line of code.

Keep you cache in check not only by LRU but by expirity time and priority too :)

Reply on news.ycombinator.com