At some point, I needed to write a function which, given a collection of product titles, picks one that is neither the longest nor the shortest, it should pick the one which best captures the essence of the product while not being excessively verbose. For example, given the product titles below, it should pick "Portable Two-Way Translator, Handheld".
Based on previous experience with centroid-based algos, the function I wrote does a first pass throwing all words from all product titles into one big bag, then computing a centroid (frequency histogram with low-frequency words removed). The second pass is to compute a cosine similarity score for each product title (its own frequency histogram against the centroid). Whichever product title is the most similar to the centroid wins.
That algo may have existed already in some academic paper somewhere, but I came up with it independently.
I tend to remember techniques more than specific algorithms, but:
One really fun algorithm involved optimizing an n^2 naive tree algorithm to O(n), ignoring logs.
For me, the way I reasoned about it was expanding the number of objects to consider (n^3), then there were observations you could apply to bring it down to O(n).
If you asked me what exactly the correspondence was between the final reduction and the original problem statement, I couldn't tell you. Maybe there was a more direct way to get to the solution.
But that style of thinking carries on with me to real tasks too. Sometimes it's easier to simplify, other times it might actually be easier to complexify, as long as you trust that you're not going down "arbitrary" complexity.
Long, long ago I came up with a text search algorithm while working on PCxRef to help technical sales support at IBM. My first approach using a naive string search took about 30 seconds on a PC. My algorithm got it down to the speed of disk access.
Basically I precomputed a table of masks and used the XLAT instruction in a very tight loop to fly though all the product descriptions for everything IBM offered back around 1983. I could accommodate case insensitivity and single character wildcards.
The test search was always "dos tech ref" to find the IBM DOS Technical reference manual.
I don't think it's complicated but I think it simplifies a complex problem I had.
A thing for storing and comparing schedules
a weekly schedule is turned into a run-length list (the week is in minutes 0 to 10079 - so 540,1020,1980,2460 would be 9am to 5pm on Sunday and Monday). Makes it easy to unpack the list into an array and do basic math comparison can determine whether schedule A is within schedule B or get the difference in minutes that schedule A falls outside of schedule B etc.
I would say the most complicated ones I've done are some SQL queries where I had to break it into stages to reduce the amount of grinding it did on a query that was combining many tables.
An auto-arrange feature for a LabVIEW/ComfyUI type DAG programming language. Could take a program with hundreds of nodes and edges and arrange them nicely so none of the lines intersected and blocks were grouped logically.
Nothing says efficiency like a sorting algorithm where Big O is more influenced by the largest element's value rather than the number of elements in the array. /s
dserban|21 days ago
Portable Two-Way Translator, Handheld
Portable Handheld Translator
Handheld Two-Way Translator
Electronic Two-Way Portable Instant Voice Translator, 40 Languages, Handheld
Based on previous experience with centroid-based algos, the function I wrote does a first pass throwing all words from all product titles into one big bag, then computing a centroid (frequency histogram with low-frequency words removed). The second pass is to compute a cosine similarity score for each product title (its own frequency histogram against the centroid). Whichever product title is the most similar to the centroid wins.
That algo may have existed already in some academic paper somewhere, but I came up with it independently.
sigbottle|23 days ago
One really fun algorithm involved optimizing an n^2 naive tree algorithm to O(n), ignoring logs.
For me, the way I reasoned about it was expanding the number of objects to consider (n^3), then there were observations you could apply to bring it down to O(n).
If you asked me what exactly the correspondence was between the final reduction and the original problem statement, I couldn't tell you. Maybe there was a more direct way to get to the solution.
But that style of thinking carries on with me to real tasks too. Sometimes it's easier to simplify, other times it might actually be easier to complexify, as long as you trust that you're not going down "arbitrary" complexity.
aleda145|24 days ago
code: https://github.com/aleda145/product_allocation_aframe/blob/m...
I'm not proud of this code, but it yielded 0.2% better result than the naive approach!
mikewarot|23 days ago
Basically I precomputed a table of masks and used the XLAT instruction in a very tight loop to fly though all the product descriptions for everything IBM offered back around 1983. I could accommodate case insensitivity and single character wildcards.
The test search was always "dos tech ref" to find the IBM DOS Technical reference manual.
LarryMade2|19 days ago
A thing for storing and comparing schedules
a weekly schedule is turned into a run-length list (the week is in minutes 0 to 10079 - so 540,1020,1980,2460 would be 9am to 5pm on Sunday and Monday). Makes it easy to unpack the list into an array and do basic math comparison can determine whether schedule A is within schedule B or get the difference in minutes that schedule A falls outside of schedule B etc.
I would say the most complicated ones I've done are some SQL queries where I had to break it into stages to reduce the amount of grinding it did on a query that was combining many tables.
pants2|23 days ago
lurker919|23 days ago
mmphosis|23 days ago
vunderba|23 days ago