|
Let's say you need to find the top 100 best-selling books out of a list of a million books.
What is the appropriate algorithm?
I thought it would be QuickSelect, but that only chooses one item.
Thank you.
|
|
|
|
|
You first need the list sorted in order.
|
|
|
|
|
If you don't want to sort the list, for whatever reason, you could always use a Max Heap structure with a heap size of 100. Iterate over your books and, if the new book has higher sales than a book in the heap, replace the bottom element with the new one. This assumes that no two book sales are going to be the same, so you would have to consider that particular wrinkle. In .NET for instance, you can use the PriorityQueue class to handle max heaps.
|
|
|
|
|
Let's say you don't want to use a SQL database, but you want to create a user data system for a web-based e-mail service.
You want to store the following data about each user:
username
password
address
alternate email address
phone number
What kind of data structure should you use?
Thank you.
|
|
|
|
|
Each individual user's information would ideally be held in a class structure for processing. You then need to decide how you save that in between references, and the obvious place is a database of some sort. The latter being especially important for security and data protection.
|
|
|
|
|
mike7411 wrote: Let's say you don't want to use a SQL database, ... data structure should you use
That is phrased incorrectly or it uses the wrong terms.
You need to store (persist) data. So you need to find a solution to that problem first.
Then you need to figure out how to store data, any data, in that persistent store.
After that then you can decide how to represent the data that you want to store (the second part of what you asked.)
Some persistent store solutions. This presumes that this project is very small and will remain that way.
- You can look at NoSQL solutions like MongoDB.
- You can learn just a little bit of SQL and use SQLite.
- You could use memcached actually. Just ignore the parts about distributed. It is just another object store.
- You could use a 'ini' file. Find an appropriate library. Odd but possible I suspect.
- Write your own simple file management library.
If you are on a course of learning and have not done any file manipulation before then the last choice is going to be best.
Note that some of the above can be used for larger projects but the business domain and architecture would be used to decide that (including a standard relational database) rather than just how simple it is to use.
|
|
|
|
|
mike7411 wrote: Let's say you don't want to use a SQL database, but you want to create a user data system for
I disagree with the previous answer and would like to hear why no SQL database, as that makes no sense at all.
I'm guessing that the "want" comes from a manager who considers MS SQL to be the only existing DB server and doesn't like the pricing. Well, simply use an Open Source SQL implementation. An SQL Server is not limited to the MS implementations.
They're optimized to store and retrieve (relational) data from a large store, and unless you want to implement a DAL yourself with indexing capabilities, constraints (like a primary key, alternate keys, non-empty constraints etc.), think about security and access rights, and a "Structured Query Language" to interact with your DAL, whilst free ones exist and the SQL language can be learned "for free" with books and sites dedicated to it - basically recreating a SQL server, you'd simply use the ones that already exist and cost you nothing. They will have less bugs than any new storage-layer you can come up with, and have a lot more manhours invested in them than your company can provide. Those are simply facts.
You use what is the most appropriate, effective and efficient; or would you choose to write a Operating System even, if there's an unexplained "want"?
Also, you do not store a password, you store a hashvalue of the password. Otherwise any employee with access to the system can dump a textfile with username/passwords on the internet.
mike7411 wrote: What kind of data structure should you use?
A table in an SQL-capable DB server.
Treat your manager like a non-technical user; if they "want" something, it has a reason and it is not always to be taken literally. You as the technical person should find out what they exactly want, why and explain the real cost and possible alternatives. This is required as "wants" and "needs" are not the same thing, and involve "costs" that a non-techie might not see. Why would anyone NOT want a FREE DAL that's well tested, well documented, in favor of creating their own?
While I'm at it, one of the columns is called "alternate email address", implying that "address" isn't an "address" but an email-address. Be specific, it makes it much more clear what you mean and removes confusion. Alternate email-address are usually not stored. Also, since you mention it is for an email-server I'd expect a table with messages, referencing that little structure you mentioned using the PK (prolly username) and another table with "attachments" stored that holds a reference to which message it is part of.
Aw, and if you really must explain this to a non-tech person, then take your time to rephrase it to be less blunt than I am in this post. Good luck with your adventure 
Bastard Programmer from Hell 
"If you just follow the bacon Eddy, wherever it leads you, then you won't have to think about politics." -- Some Bell.
|
|
|
|
|
(Odd - quote button is not working anywhere for me.)
My supposition for why they don't want to use SQL is because it is just one person messing around. So they don't want to learn it. In that case it will never be a real project.
|
|
|
|
|
I agree. And given all his posts he seems to think he can learn how to be a developer just by asking random questions here.
|
|
|
|
|
so flagstone ...[^]
In case he's interested (and needs a reason to proceed with his education) 
|
|
|
|
|
RedDk wrote: In case he's interested
So maybe you should have posted the message to the OP rather than me.
|
|
|
|
|
So sorry. I mean to emphasize the "so" here. I was only noting the deep sarcasm with which I perceived your message to be broadcasting ... and I see, having slept on my original reason for this pearl, and this morning's rodomontade from other cp agents, that msfzz is still unaware that he has a status.
No adds beyond that.
|
|
|
|
|
Could you translate that into English please?
|
|
|
|
|
Myself I didn't see any sarcasm.
Perhaps a bit of weariness though.
|
|
|
|
|
RedDk wrote: sarcasm
It is what it is. As they say.
Directly related, self-loathing and graffiti all rolled up into one pricey soccer jersey purchased down at the mall that, arter tumbling home and trying it on, turned out to be inside-out. Standing in a mirror couldn't rectify the patch situation either; they were sewn on upside-down and backwards.
Companies market this kind of thing not to be worn just spoken of at cocktail parties.
I did keep it though. And it's somewhere in the bin. And as I said to my dental hygenist back a couple of years ago, (paraphrased) "It's above the stove".
|
|
|
|
|
Don't think I agree with your sentiment.
I remember clearly when I started programming. I attempted to program things I knew nothing about. I bounced around quite a bit.
I didn't have anyone at all that I could ask questions of. I was doing stuff that I knew could be done (because I could see different but similar examples) but there was often no way to know who the authors were and no way to contact them.
Only reference material I had at all was a single magazine. Which just provided more examples.
Even once I became a professional, when there were many source materials and even when I was subjected to other people reviewing my code I still managed to produce code that I would consider horrible now.
|
|
|
|
|
We are all different, and learn differently. I learned my first programming language (very low level assembler) by copying the reference guide by hand into my own notebook. And then punching the code onto paper tape and feeding it into the system manually.
My point about the OP is that he started posting basic questions about C/C++, then moved to Java, then Java scipt, and is now onto SQL.
|
|
|
|
|
I can remember learning assembler while I was still learning C. Found it very interesting that the C compiler could output assembler and then I could use that output via C manipulation to replace a method in C with assembler and still get the same result.
First time I touched a relational database was when I used it via an API to store data. Rather certain I did not even know what 'relational' meant nor that the database did that.
|
|
|
|
|
In addition to what the others have talked about here, you may also need to think about concurrency. A DBMS (SQL or not) may handle concurrent access behind the scenes for you. Many simpler data managers will only allow a single writer, but multiple readers.
If you're going to roll your own data file manager, you are going to need to think about how to handle the situation where 2 programs want to update the data at the same time. Do you need to lock the entire data file, because you're going to re-order inserted data? Are you going to have some sort of index, so that updates/inserts only need to control access to the index and the associated record?
"A little song, a little dance, a little seltzer down your pants"
Chuckles the clown
|
|
|
|
|
Your primary consideration is: how many users does it need to support; and how many users are "logging in and out at any given time".
Then one can say what is feasible and how it will likely perform.
There are usually 3 things to consider; you only get to pick 2: cheap, fast and good.
(And for about $5 per month you could interface with a Sharepoint Online "list" ... which is transparently backed by you know what).
"Before entering on an understanding, I have meditated for a long time, and have foreseen what might happen. It is not genius which reveals to me suddenly, secretly, what I have to say or to do in a circumstance unexpected by other people; it is reflection, it is meditation." - Napoleon I
modified 18-Jan-24 13:12pm.
|
|
|
|
|
How many users? Well, considering a web based email service, the answer is "many". You will not be getting a definite number there, that will depend on the succes of the implentation, it's performance and the final pricing for the endlooser. Aw, and a little bit of marketing - it "only" has to be better or more secure than the free Proton-mail alternative.
There's no "pick 2 of these 3"; it won't be cheap nor fast, nor good, if you create your own datastorage alternative in favor of using a free product that is built solely to store and retrieve data and which has been optimized for years to do exactly that one task. In this case it is "pick 0 of these 3", literally.
Bastard Programmer from Hell
"If you just follow the bacon Eddy, wherever it leads you, then you won't have to think about politics." -- Some Bell.
|
|
|
|
|
Your assumption of "many" has no basis in fact; as do all your others. It could be a "home project". As others have pointed, OP appears to be "exploring". I was once going to build the ultimate boolean database engine.
"Before entering on an understanding, I have meditated for a long time, and have foreseen what might happen. It is not genius which reveals to me suddenly, secretly, what I have to say or to do in a circumstance unexpected by other people; it is reflection, it is meditation." - Napoleon I
|
|
|
|
|
As a home project, you'd expect "many" users (not quantifiable). He or she might be exploring, but that doesn't show in the question, does it? It asks specifically about "a web based email service". Do enlighten me, what kind of number of users would you assign to that question, besides my vague answer of "many"? Do explain?
I give no sh*t about your bool DB engine. This is the Design and Architecture Cat, and the headline speak volumes that you missed. My assumption is based on the subject line and one does not build a webbased email for five users. I'm sorry I had to explain that. How much "many" is, is not relevant to you either. It is not like Google is that different from ProtonMail. 10k users or 100M users is the same project, with more servers. It does not require a special command line compiler directive if that changes, it just requires good design. Which start by NOT WRITING A DAL. Not by inquiring to quantify what "much" is.
I never assume. Now, get off my lawn.
Bastard Programmer from Hell 
"If you just follow the bacon Eddy, wherever it leads you, then you won't have to think about politics." -- Some Bell.
|
|
|
|
|
Remember Morrissey's lyrics in The Smiths:
"It's so easy to laugh. It's so easy to hate. It takes guts to be gentle and kind."
The difficult we do right away...
...the impossible takes slightly longer.
|
|
|
|
|
I've been following his other posts; and my answer was based on his pattern. You have a pattern too.
"Before entering on an understanding, I have meditated for a long time, and have foreseen what might happen. It is not genius which reveals to me suddenly, secretly, what I have to say or to do in a circumstance unexpected by other people; it is reflection, it is meditation." - Napoleon I
|
|
|
|
|
General 
News 
Suggestion 
Question 
Bug 
Answer 
Joke 
Praise 
Rant 
Admin 
Submit an article or tip
