The "how to implement a hash table" article https://benhoyt.com/writings/hash-table-in-c/ was really helpful for me. I thought that hash tables were something that were basically impossible to make in C, but this showed that it was simpler.
When I was in university, hash tables were definitely among the things we had to learn about and then implement in C, probably in first year. Per Wikipedia, the concept dates to 1953 (with an implementation in assembly); of course people made them in C once that was an option.
I always liked that idea of just doing a linear wrap-around sweep through an array that holds (key, value) pairs, until you find the pair with the key you're looking for (for 'get' or 'contains?') or an empty spot (for 'put'). The trick to make this fast is that the hash function (key -> int) tells you at which index to start the sweep.
No secondary data structures, super simple to implement, and it works great for small use cases.
This isn't great though if you need to find out if an element exists in the table, and you have the ability to remove elements from it. I suppose you could optimize the hash table after deletions, but that again would be slow.. ?
Btw, this reminds me a bit of Cuckoo hashes. Never used them but seems like a nice idea.
The expected or amortized complexity of the standard hash table operations (put, get, contains, remove) are all O(1) for linear probing (under the usual assumptions for the hash function and as long as the table does not get too full). Of course that doesn't shield a single operation from being O(n) in the worst case.
The standard hash table has buckets, though, not just a single array that is probed through in case there's no space for a value in the slot determined by the hash function?
Right, that's the beauty of this simple approach: there's only one array and it doubles as the storage for buckets. But yes, the table will have a maximum size after which you cannot add more entries. That is, in practice you would create a new hashtable with a larger capacity and rehash all the existing entries into the new, bigger table (in practice, you would do that even sooner than that, namely when a certain load factor is passed - see my previous comment where I alluded to the role of the load factor).
The cool thing, however, is: if the size of the new hashtable is double the size of the old hashtable, your amortized insertion costs are still only O(1)!
(And you don't just have to take my word for it: take my original comment and paste it into the AI interface of your choice and have it create a concrete implementation. Ask it to add a remove operation, and an automatic doubling of the array size + rehashing when the table reaches a load factor of, say, 0.7 -- the resulting code should be very manageable, and then you can run your own tests and measure times!
This is maybe not the smartest way to do hashing, but its appeal lies in its simplicity and hence compactness of implementation. There are many cases where you don't even need a 'remove' operation, and where you never have to worry about growing the array because you know that you're only ever going to hash a certain number of elements at most.)
Let's say we have removed all elements from the hash. Then all following contains -calls will need to be O(n), if I understood correctly? They need to check every slot in the array to confirm inexistence, rather than just one bucket.
There are different ways on how to implement remove, but one way to do it is to overwrite the (key, value) pair to be removed with a special "tombstone" symbol that is different from null. Another way is to shift all elements with the same hash value as the one to be removed one index to the left, and null the final position.
There are cases where contains or get would have to iterate over the whole array, basically when all the previously added elements hash-collide, i.e., are mapped to the same start-index. But every hash-implementation has pathological cases where the access methods get slow -- but if the keys are sufficiently random, you don't expect such cases to occur in practice.
If hash tables were impossible to make in C, then it would be impossible to make them in Python, because it is a higher level language than C.
(Almost by definition, anything doable in a higher level language is doable in a lower level language, but not necessarily vice versa. In fact, many higher level languages are themselves written in lower level languages, e.g. Python is written in C.)
But Python has got dicts built into it, which are nothing but hash tables, and they are almost certainly written in C.
Google for some videos by Raymond Hettinger about Python dictionaries.
Or look at the source code of the Python interpreter.
> But Python has got dicts built into it, which are nothing but hash tables, and they are almost certainly written in C.
In CPython they are written in C (at the moment). Other Python implementations are written in other languages.
> (Almost by definition, anything doable in a higher level language is doable in a lower level language, but not necessarily vice versa. In fact, many higher level languages are themselves written in lower level languages, e.g. Python is written in C.)
It depends on what you mean by 'anything doable'. Eg Haskell compilers can in principle do lots of crazy optimisations that a C compiler would not be able to safely do, just because they don't have enough information. Even more so for Lean compilers, which can _know_ which of your loops are terminating, instead of making crude assumptions like C compilers.
Btw, higher level languages being implemented in lower level languages is mostly something for interpreters. Writing a C interpreter in Python is pretty much futile, if you care about speed. But writing a C compiler in Python is perfectly fine. And writing a Python compiler in Python is also fine. Many languages self-host (at least some of) their compilers.
The article says the last release of Jython was 2 years ago. I wonder how much it is used these days. It did seem like a good idea when it was first released. I had only tried it out a little at that time.
>It depends on what you mean by 'anything doable'. Eg Haskell compilers can in principle do lots of crazy optimisations that a C compiler would not be able to safely do, just because they don't have enough information. Even more so for Lean compilers, which can _know_ which of your loops are terminating, instead of making crude assumptions like C compilers.
Interesting. What are some of those optimisations that Haskell and Lean can do, that a C compiler would not be able to safely do?
A very simple one: in Haskell the compiler has knowledge about which functions cause side-effects and which don't. The compiler can skip calling pure functions whose return value ain't used; similarly, the compiler can call a pure function multiple times, instead of saving the return value in memory.
The Haskell compiler can also fairly freely re-arrange in what order things are computed.
A fairly common idiom in Haskell is to just return a tuple of two values, if they are 'thematically' linked; even if computing one is much more expensive than the other. The compiler is smart enough, to only compute one of the values, if you only use one of them. (When I say 'tuple', it could be literally (a, b), or it could be in a struct or whatever.)
Lean knows even more about your code, so you could do more optimisations. But you need to ask Claude for details, I haven't used it as much nor thought as much about it.
IIRC, the first edition of the book "The C Programming Language" (aka K&R), by Kernighan and Ritchie, had a simple example of how to create a hash table in C, including with buckets to handle collisions. It was a simple algorithm. It simply added up the ASCII values of all the characters in the key, modulo some number.
Yeah it's a strange assumption, as this was taught in basic data structures class years ago and any language can implement any data structure, technically speaking. C especially is a weird assumption because lots of foundational software is written in C including hash tables.
Arrays are hash tables. You can implement a very simple hash table from a tutorial, but can you implement a sophisticated one? What about a concurrent hash table?
Yeah, I'm pretty sure we made hash tables in the first C class I took in college in my second semester freshman year. If you can make a linked list, and then make an array of them, and a function to map keys to array indexes, you have a hash table. Whether it's actually performant is entirely a separate question, but a naive hash table is still a hash table.
Hash tables are awesome. They are both an incredibly simple data structure and a seriously deep rabbit hole. Most of the complexity comes from collision resolution [1], and how you handle resolution largely determines what kind of hash table you have. There are at least dozens of collision resolution approaches. The simplest, and probably the one you implemented in your undergrad C class was open addressing. That’s also what I implemented as an undergrad. But there are many more approaches, some quite a bit more complicated, and many of them let you continue to shave off asymptotic costs when you run collision resolution, or they improve locality for typical lookups, allowing better cache utilization, etc. Hash tables are super fun to play with, and for full effect, you really do need to implement them in something like C.
I only skimmed the linked article, but I do wonder whether the author ever realized that they needed to think about scope rules. I searched for the word “scope” but never found it. Closures seriously complicate language design and things get painful and counterintuitive unless you use lexical scope (or… you know… you like pain).
Yeah, I learned about a bunch of the other algorithms later (forgetting the names, but stuff like "move to the next slot rather than putting collisions into buckets" and "hash a second time if you hit a collision"; I'm sure I'm forgetting some of the nuances).
> Closures seriously complicate language design and things get painful and counterintuitive unless you use lexical scope (or… you know… you like pain)
Well if you like both lexical scope and pain, there's always lisp!
You might end up founding one of the first e-commerce sites, sell it for a handsome payday, and then create the first startup accelerator and make insane amounts of money while transforming the industry.
Maybe in JavaScript... but there is a topic called datastructures, where arrays are arrays, and hashtables are hastables. If people say this without a flip of an eye I'm not surprised why people write stuff like
> I thought that hash tables were something that were basically impossible to make in C
I have been using Audacity 3 for making music with samples for a few years. And it sort of worked, but there were a lot of things that were inconvenient, like the project sometimes not saving, or getting a "clicking" noise across clips that I had to remove by manually fading in/out each end of the clip.
I tried the Audacity 4 beta a while ago, and it seemed super clean and like it fixed a lot of stuff. I am pretty concerned about the encroaching audio.com things (even though they are completely optional), but I still think this Audacity version has promise. I especially like how you can drag clips to time-stretch them.
> or getting a "clicking" noise across clips that I had to remove by manually fading in/out each end of the clip
Are you sure this isn't just the typical "clip/crop a sample at the wrong moment, in the middle of a soundwave, and you'll get a pop/click"? This problem happens all across DAWs and hardware samplers and such, usually there is a way to "align to zero-crossings" when you wanna avoid it, or called something similar. I'd be surprised if Audacity didn't have that optionally since before, or that they didn't have it before but now with Audacity 4 it would suddenly be used automatically, that'd be somewhat strange too.
At least with Reaper, if you cut an audio clip it will, by default, automatically apply small adjustable fade in/out envelopes to the ends so you specifically don't have to manually do it.
Yeah, every software/hardware seems to deal with this differently. The sampler I use the most (Octatrack) only jumps by zero-crossings when holding SHIFT, otherwise lets you freely create entirely new pops and cracks in your songs :)
I think you're right. Audacity does have a "zero-crossings" thing, but when I tried using it a long time ago, it didn't seem to work, and I just learned to do fade-in/out for everything. Maybe I did something incorrectly.
> I just learned to do fade-in/out for everything. Maybe I did something incorrectly.
This is the de-facto standard practice for fixing/working around that particular issue, so I don't think it's incorrect at all :) Besides, however you fix an issue and it sounds good, it's correct :)
Negative reinforcement. There's a strategy for smoking where you put a wad of hair in your cigarettes. I used nicotine patches myself, so I can't speak to the efficacy.
Nit: that's not what negative reinforcement means. Negative reinforcement is about removing a negative stimulus, like inducing someone to go to a desirable website by improving their initially bad text contrast whenever they go there.
In this case, jumpscaring yourself would just be considered punishment (or "positive punishment").
* Positive reinforcement: [Adding] something so that entity does the action [more]
* Negative reinforcement: [Removing] something so that entity does the action [more]
* Positive punishment: [Adding] something so that entity does the action [less]
* Negative punishment: [Removing] something so that entity does the action [less]
P.S.: Note that this intentionally avoids diving into exactly how the Entity judges the Something. It's not always clear, even if in many cases you can guess.
P.S.: Sharing a book-quote that seems apropos, particularly the final two lines.
> People came, and tormented a nameless thing without boundaries, and went away again. He met them variously. His emerging aspects became personas, and eventually, he named them, as well as he could identify them. There was Gorge, and Grunt, and Howl, and another, quiet one that lurked on the fringes, waiting.
> [...] Howl handled the rest. He began to suspect Howl had been obscurely responsible for delivering them all to [the torturer] in the first place. Finally, he'd come to a place where he could be punished enough. Never give aversion therapy to a masochist. The results are unpredictable.
There's also Allen Carr's books about treating addiction, and they don't use negative reinforcement, at least the ones I've read
Rather it helps you learn to recognize the fallacies behind the addictive cravings themselves, and to thus resolve the core of why you turn to that in the first place
Still have to make the decision to recall those in the moment, but when you do you do neutralize the cravings
His first book was Easy Way to Stop Smoking
For digital addiction there's Smart Phone, Dumb Phone
For internet porn there's easypeasymethod.org (based on EasyWay to Stop Smoking)
I'll admit that I went quite far in your comment history to figure out if maybe those 5 closing parentheses were matching some long-lost post of yours, and as a Lisp addict you couldn't resist the temptation.
Alas, I am disappointed to inform you that your comment history will no longer compile :(
Definitely not always true. I smoke, I hate it, I've tried to quit several times. The smoke smell has never repulsed me but I find it to smell terrible. Many people I know who smoke are the same.
It's a constant reminder that you're killing yourself for miniscule amounts of Feel Good chemicals at a time.
I've always enjoyed the smell of tobacco smoke. It's nowhere near as astringent and repulsive as woodsmoke and good tobacco often has a nice nearly floral scent or a sweet smell. The taste and the tearing up my throat and making my breath bad and the expense are all things I can do without though.
Does anyone else get seasonal nicotine cravings? In the warmer months, I don't even think about smoking unless I drink, but in winter I often can't sleep for craving a cigarette, even when it's been literally years since the last one.
That is the lie you tell yourself. But smoking doesn't give you Feel Good chemicals.
It temporarily resets the clock of slowly building Feel Bad chemicals back to zero or back to lower.
Its basically the same as saying: releasing that string - that I wound around my big toe - every once in a while gives me Feel Good chemicals.
You are just relieving stress that has been created by the tobacco.
This isn't true at all, though. Nicotine is strongly dopaminergic, it directly produces euphoria.
You can describe the trap which is addiction without saying things which are obviously not true. Or, to return your uncharitable rhetoric back upon you, lying.
Thanks but I'm not really looking for advice. Where I live vape juice is exorbitantly priced. Plus there are other habitual issues with vaping, such as vaping indoors which overall increases my intake. Pouches aren't always a solution either and don't solve the "habitual" part of the habit, which is the hardest part to kick for me.
That's why the pouches are good. They reduce your craving, therefore making the act of smoking seem less necessary. Of course, the act itself is still appealing, but then you can work on reducing that habit independently and perhaps saving it for special occasions. I find cigars quite good for this. Too expensive and fancy to smoke every day but you can really treat yourself on your birthday or on holiday with something like a cigar.
Pay the higher cost for the vape or you pay with your life. If intake is increase because you will do it indoors it won't really matter, it isn't nearly as bad.
Nicotine pouches are okay, I would advise against vape though. Vape is honestly more addictive than cigarettes and I find, in large volumes, the vapour still affects my lung function. Nicotine pouches or gum are the way to go to get the benefits with minimal side effects.
I had the same experience. I vaped way more than I smoke, and it really is the nicotine that affects me the worst in the mid term. Pouches are expensive here after the tax hike and they make me feel dizzy and the gum makes me sick. I also scarred from a patch (my fault, I was dumb and left it on over a transatlantic and it chemical burned me) and they don't always work for me for some reason. Though they're my go to for when I try to quit.
I think the habit of actually smoking is the hardest for me to kick. The small break is what keeps me going and clears my head, especially during work, and it's hard to replicate that.
I’ve never experienced crude oil firsthand, but I assume you are talking about “sour crude” which has a high sulfur content, including hydrogen sulfide, resembling rotten eggs or raw sewerage. So-called “sweet crude”, with a low sulfur content, has a less offensive smell, smelling more like the petroleum products derived from it.
It is hilarious that page shows how one replaces FB with HN... which is precisely what I did in 2019, and now I'm a total HN addict, spending more than a few minutes on it at least 5 times a day.
in case you don't know this only has limited effect, cause you can open it again in a private browser. besides the search works with the procast setting, and we're not talking external constraints, people, us, me,... lack at this point internal mental defenses against the negative impact of social media.
See, this is the problem with all these mindfulness tools. I, the human, can simply defeat every challenge the computer attempts. And i require the ability to do so in case i have a need that's only satisfied by searching reddit for textbook recommendations while I'm in half price books, or a youtube video to fix my broken zipper pocket before i head to the gym soon. The fact that they time wasting sites are also the "goldmine of knowledge" sites make me include a back door in any time minder tool. A backdoor which is only used when needed... until it slowly becomes muscle memory and the tool is defeated by my capacity to learn to fuck myself over again and again.
Instead you ought to pay someone $15/hr to sit next to you. Anytime you're distracted by a website for more than five minutes, they punch you in the arm.
They also have to know they don't get paid if you manage to convince them to go away and leave you alone for a while.
Someone should to invent an AI powered one that is utterly unpredictable and installs in the boot sector. You're browsing Hacker News one day and suddenly your smoke alarms goes off. You do it the next day and your Echo device starts playing death metal at highest volume. You do it the next day and your car alarm goes off.
It unsettled me a lot about just how much work was put into making the JavaScript version of this work instead of a purely Python version, due to how OpenCV works. I wonder how universal the laggy OpenCV thing is, because my friend faced it too when working on an OpenCV application. Is it so unavoidable that the only option is to not use Python? I really hope that there is another way of going about this.
Anyways, I am very glad that you put in all that effort to make the JavaScript version work well. Working under limitations is sometimes cool. I remember having to figure out how PyTorch evaluated neural networks, and having to convert the PyTorch neural network into Java code that could evaluate the model without any external libraries (it was very inefficient) for a Java code competition. Although there may have been a better way, what I did was good enough.
Creating a faster python implementation can definitely be done. OpenCV is a thin wrapper over the C++ API so it's not due to some intrinsic python slowness. It is not easy to resolve though and I suspect the way python code is typically written lends itself to an accidentally blocking operation more often than JS code. It's hard to know without seeing the code.
author here, sorry you have to see my janky JavaScript solution XD
but one good thing of going with Tauri is that developing the UI is pretty easy, since it's basically just some web pages, but with access to the system, through the JS <-> Rust communication.
also, rewriting neural network from PyTorch to Java sounds like a big task, I wonder if people are doing ML in Java
A few weeks ago, I tried to compile Clang to WebAssembly, but got several different errors, and tried fixing a lot of them, but some of them seemed kind of impossible to fix, so I thought I would try again at a later date. However it seems I will not need to try again. I feel angry that someone made a convenient solution before I did, but also happy, because this probably implies that they made a consistent process to compile Clang for WASM.
I looked up what "the sentinel" was, and it turns out it was a game in 1986, that works on the BBC Micro and Commodore 64, and has 3D graphics! I didnt even know it was possible to do that on average computers in 1986!
There was no texture mapping, and the 'trick' that makes it work is that all you can do is rotate/pan in place. The only movement is instantaneous teleportation.
The world procedural generation from a seed alone is amazingly well implemented in an environment so constrained most programmers nowadays wouldn't even be able to do anything in.
The online SAT was much easier than the written version, because (1) You don't have to read big essays anymore in the reading part, and (2) both math sections have the Desmos graphing calculator, with absolutely no features taken out. Desmos is far more convenient to use than a TI-84 for many things, so it made all the problems, especially the hard ones, much easier.
Also, in my opinion, their Bluebook testing software is actually pretty good, especially compared to other digital testing software I had to use over the years, like ClearSight.
I am so impressed that you were able to figure so many things out in the puzzle! I feel like I would never be able to do that, but I feel like all that is needed is a lot of patience, a lot of time, and a lot of deep thought.
I would subscribe to Byte, DDJ, Creative Computing, and Scientific American (pre-1990 to be generous, maybe pre-1970 if I'm not), if their equivalents existed today.
