|
Thread Rules
1. This is not a "do my homework for me" thread. If you have specific questions, ask, but don't post an assignment or homework problem and expect an exact solution.
2. No recruiting for your cockamamie projects (you won't replace facebook with 3 dudes you found on the internet and $20)
3. If you can't articulate why a language is bad, don't start slinging shit about it. Just remember that nothing is worse than making CSS IE6 compatible.
4. Use [code] tags to format code blocks. |
I have a set of node-weight pairs. So, each node corresponds to a weight.
In each loop, I traverse the nodes in sorted order (minimum to maximum) and do some math stuff.
After every loop, the weight of any of my nodes may change.
What is a very fast design for doing this?
Right now I am using http://www.grantjenks.com/docs/sortedcontainers/sorteddict.html
A sorted dictionary, where I map weights to the node. Then traverse the keys which the dict presents in sorted order.
With this approach, I must delete and re-add new key-value pairs at every step.
But, if I want my weights sorted, any implementation must either sort or start from an empty structure. I can't expect values to magically sort as I re-assign them.
So I wonder if it's even possible to get much faster than what I am using right now. The only thing I could think of is some sort of heap, where I heap the weights and the nodes are glued to them.
Maybe you guys have some clever idea or structure I don't know about.
|
On March 07 2018 08:28 travis wrote:I have a set of node-weight pairs. So, each node corresponds to a weight. In each loop, I traverse the nodes in sorted order (minimum to maximum) and do some math stuff. After every loop, the weight of any of my nodes may change. What is a very fast design for doing this? Right now I am using http://www.grantjenks.com/docs/sortedcontainers/sorteddict.htmlA sorted dictionary, where I map weights to the node. Then traverse the keys which the dict presents in sorted order. With this approach, I must delete and re-add new key-value pairs at every step. But, if I want my weights sorted, any implementation must either sort or start from an empty structure. I can't expect values to magically sort as I re-assign them. So I wonder if it's even possible to get much faster than what I am using right now. The only thing I could think of is some sort of heap, where I heap the weights and the nodes are glued to them. Maybe you guys have some clever idea or structure I don't know about.
Can multiple nodes have the same weight? If so, a sorteddict won't work.
Either way, a sorted dict in that way probably uses a heap as the underlying data structure anyway. If I had to implement it from start, I'd probably use a binary heap of tuples (weight, node), with the sort only on the weight, obviously. Maybe a Fibonacci heap if delete operations are few and far between. Most heaps can work with duplicate values.
|
It should be noted that no ethically-trained software engineer
would ever consent to write a DestroyBaghdad procedure.
Basic professional ethics would instead require him to write
a DestroyCity procedure, to which Baghdad could be given as a parameter.
|
On March 07 2018 22:58 Manit0u wrote:It should be noted that no ethically-trained software engineer
would ever consent to write a DestroyBaghdad procedure.
Basic professional ethics would instead require him to write
a DestroyCity procedure, to which Baghdad could be given as a parameter.
I'm sure that there's some pun involving constructors / destructors to be made here.
|
On March 07 2018 22:58 Manit0u wrote:It should be noted that no ethically-trained software engineer
would ever consent to write a DestroyBaghdad procedure.
Basic professional ethics would instead require him to write
a DestroyCity procedure, to which Baghdad could be given as a parameter.
Haha, hilarious! Where's that from?
|
|
|
working on my state-machine library (c++). recently i wrote a random-generation module (of dfa, nfa-graphs or expressions).
i exposed it through a RESTful web-api (i think), using boost beast to write a tiny server. boost beast seems like a great addition to the boost libraries. maybe it could do with a more detailed model of the uri. then wrote a simple gui (html/css/js) that fetches a random graph (layout done server-side with ogdf) and draws it using sigmajs (also neat). this is my first foray into javascript, it seems totally crazy, but also quite careless and free.
below are two examples of nfa-graphs over a binary alphabet, with colors from solarized theme. note that the top-most automaton has initial states in each connected component, it is the graph of one nfa. it's a bit hard to decipher the automaton (doesn't show transition symbols f.ex.), but it is just for show.
![[image loading]](https://i.imgur.com/3pxBDxT.png)
![[image loading]](https://i.imgur.com/nu71clQ.png)
i was contemplating writing everything in c++, or doing c++/python or c++/web. i chose the c++/web approach because i haven't tried it before. the c++/python stack seems super-nice as well though, especially considering how easy it is to set up bindings twixt c++ and python with pybind or boost python, and also considering how low-tech a python environment can be, and also the versatility of python wrt build-processes, deployment and testing. the pure c++ approach seems a bit of a hassle at the moment. i didn't get friendly with any of the gui-toolkits yet. i'd try emscripten, but it uses clang, and doesn't support concepts yet.
i suspect there are some well-versed web-devs in this thread. i was wondering about your thoughts on letting a resource in REST refer to an operation. i am a bit confused here, as i have seen some articles contrasting REST with f.ex. RPC-JSON. this contrast only seems to make sense if resources are not allowed to be operations.
f.ex. i exposed my random generation like this:
http://host:port/rand/{graph,expr}/{dfa,nfa}
the server responds to a GET on this url by computing a random automaton of the designated type and return it. i probably want to parametrize the random generation. if i were to encode the parameters in the query, it seems the only difference between this and RPC-JSON would be the format of the parameters (encode in query vs JSON-format body), and maybe the verb of the request? this seems sort of irrelevant so i suspect i am missing something, and remember i am new to this.
|
REST logically maps to a database/object model (i.e. CRUD operations), while RPC logically maps to a function call (i.e. other operations).
If you want an API to make a function call on your server you want RPC (which stands for Remote Procedure Call). You can accomplish the same things in either but one or the other makes it logically simpler depending on your use case.
Your JSON-RPC call might look like:
http://host:port/generateRandomGraph
with a body of:
{
"graph": "dfa",
"expr": "nfa"
}
Your understanding of the difference between RPC and REST seems right. Google "REST vs RPC" to get a more detailed explanation. There is a lot of discussion on the difference.
|
On March 10 2018 05:02 nunez wrote:
i suspect there are some well-versed web-devs in this thread. i was wondering about your thoughts on letting a resource in REST refer to an operation. i am a bit confused here, as i have seen some articles contrasting REST with f.ex. RPC-JSON. this contrast only seems to make sense if resources are not allowed to be operations.
f.ex. i exposed my random generation like this:
http://host:port/rand/{graph,expr}/{dfa,nfa}
the server responds to a GET on this url by computing a random automaton of the designated type and return it. i probably want to parametrize the random generation. if i were to encode the parameters in the query, it seems the only difference between this and RPC-JSON would be the format of the parameters (encode in query vs JSON-format body), and maybe the verb of the request? this seems sort of irrelevant so i suspect i am missing something, and remember i am new to this.
I've spent a good couple years fighting with this, trying to read through the internet and determine what is "right" and how to do things. It's important to remember that REST is just an architectural style, it doesn't necessarily tell you specifics on how to implement but more guiding principles.
In a REST world, there are only nouns. Everything is a resource. From my interpretation of REST -- if that is the direction you ultimately wanted to go -- there are a few things that stick out as needing to be changed.
In your example, the automaton is the resource. GETs are supposed to be idempotent and cannot modify server state. Generating an automaton as a result of a GET request is therefore a no no. Also, each context path is suppose to be another resource -- the fact that it's random, {graph | expr}, {dfa | nfa} are all attributes of the automaton, they don't seem to be resources of their own. In the new scheme, one could POST to /automatons with the parameters needed to create one which could return an id that could be retrieved later via a GET
If you don't like that, another way that I've found that people semantically get around the fact that verbs do not exist is that there are events. A generate automaton event is a noun and something that can be created. Similarly to before you would POST the params to the automaton creation event that returns a link to the newly created resource.
You can keep going down this path, but, even though REST is one of the hot buzzwords, it's why I've ultimately iterated to the fact that most people don't actually want a RESTful api in it's purest definition. There are a ton of great principles in REST as applied to http -- using HTTP verbs correctly, using media type to represent the type of content flow, etc ... but I personally find that pragmatically most of us think in verbs and operations.
There are also other tradeoffs like it's just harder to test POSTs than it is GETs, harder to share with people a single link to show off, especially if you are new to all this and just want to test or show off that just by supplying different params you can generate different automaton. I'd personally just do what works and leave out the "correctness" for a later point -- but if you want to do it "right' hopefully this was helpful.
this seems sort of irrelevant so i suspect i am missing something, and remember i am new to this.
:D tech people and their purity... good luck fighting this one for a long time
|
thanks for replies, very helpful.
the random-generators for each type of automaton (graph-dfa,graph-nfa,expr-dfa,expr-nfa) is modelled as resources. rand, rand/expr and rand/graph are all collections, whilst f.ex. rand/graph/dfa is the random-generation algorithm as a resource. {graph,expr} refers the form of the automaton, whilst {dfa,nfa} refers to the content, neither are attributes (at least not in the state-machine theory i am familiar with). the attributes of an automaton are it's states, transitions, etc, which i did not bother to expose.
another part of the API exposes the actually existing automatons (store/my_neat.graph_dfa, store/my_neat.graph_nfa), but it is irrelevant to this discussion.
the kicker is that a GET on one of the generators returns the result of a generation, and not the generator itself. that is, the algorithm doesn't modify the server-state when you GET rand/graph/dfa, it generates an automaton and replies with it. the generation is const with respect to server state. if it stored the generated automaton on the server, then it would be abusing GET. i should have been more clear on this.
again my confusion loops back to whether or not you can model operations / algorithms / functions as a resource, which i have not found a clear answer too. is it an abuse? is the 'pureness' of your REST-api a metric of how similar the object (what is being modeled) is to CRUD? then i can see the allure of a pure REST-api... not in REST itself, but in the simplicity of its object.
the event-based approach was new to me, very interesting.
i try to be pragmatic above all, so i won't lose any sleep over this in any case. i am learning the concepts is all.
|
On March 10 2018 22:51 nunez wrote:
thanks for replies, very helpful.
the random-generators for each type of automaton (graph-dfa,graph-nfa,expr-dfa,expr-nfa) is modelled as resources. rand, rand/expr and rand/graph are all collections, whilst f.ex. rand/graph/dfa is the random-generation algorithm as a resource. {graph,expr} refers the form of the automaton, whilst {dfa,nfa} refers to the content, neither are attributes (at least not in the state-machine theory i am familiar with). the attributes of an automaton are it's states, transitions, etc, which i did not bother to expose.
another part of the API exposes the actually existing automatons (store/my_neat.graph_dfa, store/my_neat.graph_nfa), but it is irrelevant to this discussion.
the kicker is that a GET on one of the generators returns the result of a generation, and not the generator itself. that is, the algorithm doesn't modify the server-state when you GET rand/graph/dfa, it generates an automaton and replies with it. the generation is const with respect to server state. if it stored the generated automaton on the server, then it would be abusing GET. i should have been more clear on this.
again my confusion loops back to whether or not you can model operations / algorithms / functions as a resource, which i have not found a clear answer too. is it an abuse? is the 'pureness' of your REST-api a metric of how similar the object (what is being modeled) is to CRUD? then i can see the allure of a pure REST-api... not in REST itself, but in the simplicity of its object.
the event-based approach was new to me, very interesting.
i try to be pragmatic above all, so i won't lose any sleep over this in any case. i am learning the concepts is all.
But your GET still wouldn't be idempotent. Multiple calls to /rand/graph/nfa would produce different results I'm assuming since it says random.
I was using the term modifying state too loosely. I guess what I meant is you still created something. Even though you are not storing the results from a random generation it is still creating the results. Not just reading it.
|
i assumed the idempotency was defined wrt resources, and not responses. the resource, on the server, or the state of the server itself, does not change, but the response sent back to the client is different every time.
consider f.ex. the inclusion of a date-field in the response: it might differ for each corresponding request.
|
|
|
I've not done much C++ since I started a new job. Probably about 3 weeks except reading some code. Do you guys feel the need to do some warm-up like me? What helps to regain confidence, I mean what kind of exercise do you go for? Some fun project I guess? I expect to start using C++ in the near future though.
|
On March 11 2018 08:19 sc-darkness wrote:
I've not done much C++ since I started a new job. Probably about 3 weeks except reading some code. Do you guys feel the need to do some warm-up like me? What helps to regain confidence, I mean what kind of exercise do you go for? Some fun project I guess? I expect to start using C++ in the near future though.
Depends a bit. I'm equal fan of just jumping in and be super slow the first few weeks until I get confident again. Unless you're starting from scratch it's going to take that long to learn the code you're jumping into anyways. But otherwise, yeah, just do some projects you might find fun! I just did a bunch of Unity stuff because I wanted to touch up on C# myself.
Otherwise, there's always Codewars 
|
new trends on web programming emerge faster than I can forget the old ones.
just a few years ago I was learning jsf 1.2 and then it went like
jsf 1.2+richfaces -> jsf 2+primefaces -> extjs -> angularjs -> angularjs 2-3-4 -> react -> whatever the hell is trendy right now
I just want to settle down and get proficient in something. It is so pointless to learn to put down the same damn button in 24 different ways.
|
Hyrule19152 Posts
yeah that's because you're just trying to learn the newest thing instead of learning just the ones you need. Angular, Vue, and React are all still popular, but each serves a different role. Pick the framework for the job, or pick a framework and take jobs based on that (if you're a contractor or work an agency or something).
|
On March 11 2018 02:00 nunez wrote:
i assumed the idempotency was defined wrt resources, and not responses. the resource, on the server, or the state of the server itself, does not change, but the response sent back to the client is different every time.
consider f.ex. the inclusion of a date-field in the response: it might differ for each corresponding request.
An easy way to reason about GET vs POST is to remember that the client (browser) is allowed to cache the response of a GET query. If that affects your expected behavior, GET should be avoided.
|
On March 11 2018 10:32 Hanh wrote:Show nested quote +On March 11 2018 02:00 nunez wrote:
i assumed the idempotency was defined wrt resources, and not responses. the resource, on the server, or the state of the server itself, does not change, but the response sent back to the client is different every time.
consider f.ex. the inclusion of a date-field in the response: it might differ for each corresponding request. An easy way to reason about GET vs POST is to remember that the client (browser) is allowed to cache the response of a GET query. If that affects your expected behavior, GET should be avoided.
I have been wondering about this, too. I'm working on something that is similar to a forum in a SPA. The content of a thread necessarily changes over time. So when I request a certain thread (all its comments), do I use a GET (bad because of caching) or a POST (doesn't seem to be what POST is supposed to be for).
|
In your case, I'd use GET with a Cache-Control header (or something to the same effect) because you are expecting every user to see the same result, i.e. the user is getting the latest snapshot of the resource.
However, in the OP the user will get something different every time. I'd use POST because it seems that the user is "posting" a request for a new graph. If instead the url was of the form /rand/graph/nfa?seed=xxx then I think GET would be fine.
|
|
|
|
|
|
EPT
