|
The strings are determined at runtime so building a DFA is not desirable.
Edit: It might be possible to pre-bake DFAs for predefined queries but that would be more of a code generation thing. The thing is I don't have the RAM for DFA tables so I'd need it to be compiled.
Real programmers use butterflies
|
|
|
|
|
How about creating a tree from the list of strings characters. Then you could attempt to traverse the tree as the characters come in and if you get to a leaf, you have a match. If you would need to buffer a bit so you can backtrack, but I think you know how to do this.
"Time flies like an arrow. Fruit flies like a banana."
|
|
|
|
|
The biggest concern is RAM. Speed is secondary. I need to use as few bytes as possible for this. The strings are already allocated because 99% of the time the passed in strings are constant so i don't waste bytes reallocating them in a different form. I suppose I could turn the list of strings i'm using into a tree but there are fewer than 5 strings for the average query. Usually one or two, maybe three.
Real programmers use butterflies
|
|
|
|
|
I have a slight suspicion that this 'minimal RAM' has become an obsession with you. I have been working with embedded processors for 10+ year, and seen how available resources have grown for off-the-shelf embedded chips. 10+ years ago, IoT was not a concept, but those chips (or rather: their successors) I worked with ten years ago are those used in IoT things today. Today they are capable, low power, modern.
If you look upon yourself as a masochist, you may of course go for something like a 2903 four-bit bit slice processor (really intended for combining 4 or 8 to a 16- or 32-bit CPU), where you have to write the microcode yourself. If you are not quite as much a die-hard masochist, you may go for an 8-bit CPU with 16 bits memory bus, but only 4096 bytes allocated to RAM.
That is for masochists only. Not The Way to solve a problem, create a solution. If you really need to implement an IoT solution, there are numerous processor alternatives giving you access to lots of resources way beyond what your are talking about.
Your attitude reminds me of the very first international conference I ever visited, on free text search, where one paper showed how they had succeeded in reducing the space requirement for index terms by (slightly less than) one bit per index term. Maybe the technology was great that year, but I have never heard of them later.
For being blunt: Anno 2020, no solution will earn everlasting accolade because it fit in 4K RAM. Not even 16K RAM. If you move up to 64K (or more), that is what everybody is doing. Nothing special about that.
'I managed to fit it into 4K!' is a battle arena left long ago. Sure: Some groups have developed it into an extreme art - you will find a huge collection at pouët.net[^]. One of my favorites is Skyline[^] - do download it to see what they managed to squeeze into 4096 bytes - it it totally unbelievable!
But that is not 'problem solving', not 'usable' in any way. It is just show off: Ain't I clever? Yes, you are, and impressively so.
Now, let us go back to productive world. Let us solve real world problems of today, using tools of today.
|
|
|
|
|
I am targeting 32-bit arduinos. Eventually I will target the 8 bit ones - most of my code is 8 bit ready but i'm saving actually targeting them for now. Regardless, i wanted to get the ram use realistic for those devices
They have varying amounts of ram. The Atmega2560 has 8kB. some others have 32kb. My current monster is 32 bit and has 520kb but that's an exception, not the rule, and it has multiple cores so i'm not the only thread using ram anyway.
I do enjoy the challenge, but it's not for nothing.
Edit: Also, so far I have only been doing very simple queries out of large documents. The less memory they take per, the more complex queries I can compose with them.
Atmegas still sell. ArduinoJson is still used all the time. I have to disagree with you.
Real programmers use butterflies
modified 18-Dec-20 20:32pm.
|
|
|
|
|
honey the codewitch wrote: I will target the 8 bit ones - most of my code is 8 bit ready but i'm saving actually targeting them for now OK, go ahead, but I have a feeling that you are spending resources on designing improved horseshoes.
|
|
|
|
|
I would disagree, as I suspect the author of the popular ArduinoJson library would as well.
Real programmers use butterflies
|
|
|
|
|
honey the codewitch wrote: this is one of the weirdest things i've written in a long time Definitely not
|
|
|
|
|
I'm with you. Strings are always compared one character at a time anyway. Write a custom string comparer.
|
|
|
|
|
I've only glanced at the article, but CP's Daily News this morning pointed out that Google had purchased a company that "turns your old Windows 7 PC into a Chrome OS machine".
How old are we talking about? Chrome, the browser, is a pig, no matter what the underlying OS might be. The most resource-hungry thing you can ask an old box to do is to run a web browser--even the simplest pages nowadays download a few MBs worth of crap, and the scripting built into them to manipulate the content on the fly makes the poorly-performing apps of yesteryear look snappy in comparison.
The moment Edge switched to being Chrome-based, it became as much of a hog. I'm not blaming MS for that - something about pigs and lipstick.
I'm all about repurposing old systems and giving them new life. I'm getting to like Linux a lot for that. But where things start to fall apart is when you load a resource-hungry browser. I've witnessed this first-hand more times than I care to count: A clean Windows 7 system with IE performs better than a lean Linux distribution with Chrome. Of course, IE is no longer a contender, but we're quickly running out of viable alternatives.
Bottom line - if you want to give an old system a new lease on life, browsers will get you right back onto square one, again, no matter what the underlying OS is. And I don't know of a good solution for that. And that kinda sucks, because you can no longer just give grandma an old system "just for email and Facebook".
|
|
|
|
|
Maybe far in the future webassembly will run in hardware, and then we'll just have webassembly machines with basically a minimal OS behind it.
But maybe that would be worse than the current state of things.
Real programmers use butterflies
|
|
|
|
|
I did just that with an old Windows 7 laptop over a year ago. It worked fine.
|
|
|
|
|
"That"?
Linux, or ChromeOS?
|
|
|
|
|
|
Now I'm curious. I thought Google went out of its way to prevent the average guy from just downloading an ISO and installing on random hardware. Has this changed?
|
|
|
|
|
Not sure what that has to do with the question.
|
|
|
|
|
Consider it its own question then. Has Google started making ISO files available for anyone to download and install on random hardware?
|
|
|
|
|
Sorry, I still do not know what you mean.
|
|
|
|
|
Do you not know what an ISO file is?
Here's one, but I'd rather download from a site owned by Google than..."this".
|
|
|
|
|
Yes, of course I do, and I have used them often over the years to make CD images of both Windows and Linux distributions. But I still do not know what point you are trying to make.
|
|
|
|
|
Really? I spell it out rather clearly a number of times throughout this thread.
I was under the impression that there was a point in time, at least initially, when Google apparently didn't want people to just download an ISO of the OS and install it on their own hardware; they'd rather have people buy Chromebooks with the OS preloaded (kinda like Apple goes it out its way to prevent people from downloading their x86-based OS and run it on non-Apple hardware).
I did not realize that this had changed (or was ever a thing to begin with). As per my last message, it does seem like they've relaxed the rules somewhat and you can download an ISO easily enough (I had never tried very hard), if you can find/trust the repositories for it.
I was just asking about that; I wasn't trying to "make a point".
|
|
|
|
|
Well possibly there was such a point in time. Either way I got the download, but I'm not sure whether it was direct from Google or elsewhere.
|
|
|
|
|
That'd be good to find out. A quick search yesterday brought up the page I had linked to, but it looks to me like they have no affiliation whatsoever with Google themselves. Not sure I wanna run an OS if I can't trust where it originates from.
|
|
|
|
|
Which was exactly why I loaded it onto an old laptop which contained no personal information. It was a proof of concept project that I was involved in, prior to the rollout of real Chrome boxes.
|
|
|
|
|
Well, of course I'd only install an OS on a system that starts life with nothing of value on it (I quit doing in-place upgrades and multi-booting the moment I started using VMs). But once you start connecting to other things, all bets are off again. Especially with an OS like ChromeOS that you can't do much with if you don't link it with an online profile.
So I just tried the experiment. Went to Google, searched for "chromeos iso download". The top links are:
- A reddit page (WHY???)
- getchrome.eu, which describes itself as "a lightweight Linux distribution similar to Google Chrome OS" (so clearly, it's NOT ChromeOS, but some clone)--and the ISOs are hosted on dubious sites that try to get you to "upgrade to Pro for faster downloads" or misdirect you into downloading unrelated stuff. The bottom of the page even confirms, "Cr OS Linux is not related to Google".
- sites.google.com, which links to the site above (if they're not related, then WHY??)
- a superuser.com discussion on where to get an ISO (pretty much my own question)
- neverware.com, which seems to push for a commercial, pay-for version (which again, sounds like something that was forked)
- more dubious sites like cnet and softonic, which are known to wrap their own installers around whatever you're trying to download
The most promising of these is the superuser.com answer (aka "the StackOverflow for IT admins"), and the discussion is closed and marked off-topic. The responses all point to pre-made VMware and VirtualBox images and the like, and not something that runs natively on bare metal.
If Google is okay with letting people download ChromeOS and run it on non-Chromebooks, they sure are taking exceptional steps to remove it from the top of the search list. This, from a company that is currently facing lawsuits for promoting their own products and services over its competitors. So WTH is going on?
|
|
|
|