And then thousands of people start relying on that bit of useless code, which in turn ruins thousands of projects when they stop supporting it.
edit: Also, it has a dependency to this repo: https://github.com/sindresorhus/noop3 Brilliant
Forum Index > General Forum |
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. | ||
Excludos
Norway7685 Posts
March 29 2018 13:10 GMT
#19041
And then thousands of people start relying on that bit of useless code, which in turn ruins thousands of projects when they stop supporting it. edit: Also, it has a dependency to this repo: https://github.com/sindresorhus/noop3 Brilliant | ||
Deleted User 3420
24492 Posts
April 02 2018 14:54 GMT
#19042
I can describe it like this. I have a graph, it has an undetermined amount of edges, and nodes 0 to n. For an example, let's say it has nodes 0 to 9. So, 9 nodes. I take a subset of these nodes. Let's say I take nodes 2,3,4,5. What I do in my program is I take this subset, and I mark each node in the subset that has an edge that connects to a node that is not in the subset. For example, if 2 goes to 3,5,8 - it would get marked, because it has an edge that connects to 8 which is not in the subset. But if 3 goes to 2,4,5,and nothing else - it would not get marked. Now I take my subset, and I BFS all simple paths (paths that touch each node once), within my subset, that *start and end* on a marked node. So, it could be said that what I am doing is finding paths that go through my subset, connecting to each node in it, and is able to continue on through the graph in both directions. For every pair of marked nodes, I map that pair to a list, and the list is populated with sets of edges that make up a path I found. Maybe I don't find any paths that qualify for a given pair, or maybe I find 100,000 paths that qualify for a given pair. So I have something like map[2,4] -> [{(2,3),(3,5),(5,4)}, {(2,5),(5,3),(3,4)}] map[3,4] -> [{(3,2),(2,5),(5,4)}] map[4,5] -> [{}] ... etc Now - to the actual problem. For any list that has at least one path, I only actually need one path. Not 2, and not 100,000. But for the entire subset I am finding paths for, I want to use as few edges as possible to make up all these paths. So basically, I want to pick the fewest amount of edges I can, such that I can form at least one path from every list that has a path. I recognize that this is... a difficult problem to do exactly. So, I am more focused on efficiency than precision. Getting a set of edges that is a little too big in time k^3 (where k is the size of my subset), is way way better than an exact answer in say k^2*2^k, for example. Any ideas? I think my first step must be to sort my lists by number of sets, and look at the lists with only one set, and do intersection of all of those because I need those edges. Then I can worry about finding missing edges to be able to make a set from all the other lists. But even that is difficult. This is what I went with... + Show Spoiler + I store the required edges in a set and return it. paths is a dictionary of lists, so k is a key of (start_node, end_node)
| ||
Neshapotamus
United States163 Posts
April 03 2018 01:09 GMT
#19043
On April 02 2018 23:54 travis wrote: need help. this is probably the hardest problem i've had to address while programming. I can describe it like this. I have a graph, it has an undetermined amount of edges, and nodes 0 to n. For an example, let's say it has nodes 0 to 9. So, 9 nodes. I take a subset of these nodes. Let's say I take nodes 2,3,4,5. What I do in my program is I take this subset, and I mark each node in the subset that has an edge that connects to a node that is not in the subset. For example, if 2 goes to 3,5,8 - it would get marked, because it has an edge that connects to 8 which is not in the subset. But if 3 goes to 2,4,5,and nothing else - it would not get marked. Now I take my subset, and I BFS all simple paths (paths that touch each node once), within my subset, that *start and end* on a marked node. So, it could be said that what I am doing is finding paths that go through my subset, connecting to each node in it, and is able to continue on through the graph in both directions. For every pair of marked nodes, I map that pair to a list, and the list is populated with sets of edges that make up a path I found. Maybe I don't find any paths that qualify for a given pair, or maybe I find 100,000 paths that qualify for a given pair. So I have something like map[2,4] -> [{(2,3),(3,5),(5,4)}, {(2,5),(5,3),(3,4)}] map[3,4] -> [{(3,2),(2,5),(5,4)}] map[4,5] -> [{}] ... etc Now - to the actual problem. For any list that has at least one path, I only actually need one path. Not 2, and not 100,000. But for the entire subset I am finding paths for, I want to use as few edges as possible to make up all these paths. So basically, I want to pick the fewest amount of edges I can, such that I can form at least one path from every list that has a path. I recognize that this is... a difficult problem to do exactly. So, I am more focused on efficiency than precision. Getting a set of edges that is a little too big in time k^3 (where k is the size of my subset), is way way better than an exact answer in say k^2*2^k, for example. Any ideas? I think my first step must be to sort my lists by number of sets, and look at the lists with only one set, and do intersection of all of those because I need those edges. Then I can worry about finding missing edges to be able to make a set from all the other lists. But even that is difficult. This is what I went with... + Show Spoiler + I store the required edges in a set and return it. paths is a dictionary of lists, so k is a key of (start_node, end_node)
| ||
Deleted User 3420
24492 Posts
April 03 2018 04:18 GMT
#19044
| ||
Apom
France654 Posts
April 03 2018 07:26 GMT
#19045
On April 02 2018 23:54 travis wrote: ... I recognize that this is... a difficult problem to do exactly. So, I am more focused on efficiency than precision. Getting a set of edges that is a little too big in time k^3 (where k is the size of my subset), is way way better than an exact answer in say k^2*2^k, for example. ... Then take every edge in the subset, can't beat O(1) efficicency. | ||
gravity
Australia1721 Posts
April 03 2018 10:35 GMT
#19046
| ||
Deleted User 3420
24492 Posts
April 04 2018 18:07 GMT
#19047
On April 03 2018 16:26 Apom wrote: Show nested quote + On April 02 2018 23:54 travis wrote: ... I recognize that this is... a difficult problem to do exactly. So, I am more focused on efficiency than precision. Getting a set of edges that is a little too big in time k^3 (where k is the size of my subset), is way way better than an exact answer in say k^2*2^k, for example. ... Then take every edge in the subset, can't beat O(1) efficicency. heh well, the entire point is to eliminate as many edges as possible, so while I like your sass I don't think this is a good solution On April 03 2018 19:35 gravity wrote: Could you use a search algo like A*? (Whether this is efficient enough will depend on the shape of the data, but it will probably be ok). Well the way I traverse is not an issue, the issue is eliminating unneeded edges from the lists of paths found. Unless you've got something clever in mind I am not thinking of. Anyways I moved past this issue, though I would still be interested in any sharp solutions. | ||
Silvanel
Poland4601 Posts
April 05 2018 07:43 GMT
#19048
| ||
Acrofales
Spain17187 Posts
April 05 2018 08:25 GMT
#19049
On April 03 2018 13:18 travis wrote: It is not because a minimum spanning tree can touch nodes more than once, and I need paths that only go to/from them once. Pretty sure an MST is the solution you're looking for. Between any two nodes in an MST there is exactly one path (from the first node up to the shared parent and then down to the other node). And all nodes that are connected in the greater graph, are connected in the MST. Moreover, it is optimal in the number of edges. | ||
Deleted User 3420
24492 Posts
April 05 2018 15:14 GMT
#19050
On April 05 2018 17:25 Acrofales wrote: Show nested quote + On April 03 2018 13:18 travis wrote: It is not because a minimum spanning tree can touch nodes more than once, and I need paths that only go to/from them once. Pretty sure an MST is the solution you're looking for. Between any two nodes in an MST there is exactly one path (from the first node up to the shared parent and then down to the other node). And all nodes that are connected in the greater graph, are connected in the MST. Moreover, it is optimal in the number of edges. I don't think so because for a given set of nodes I am only looking for paths that go through all those nodes one time. While a minimum spanning tree will give me a path, it generally won't give me ones that go through all the nodes in the set. | ||
Acrofales
Spain17187 Posts
April 05 2018 19:24 GMT
#19051
On April 06 2018 00:14 travis wrote: Show nested quote + On April 05 2018 17:25 Acrofales wrote: On April 03 2018 13:18 travis wrote: It is not because a minimum spanning tree can touch nodes more than once, and I need paths that only go to/from them once. Pretty sure an MST is the solution you're looking for. Between any two nodes in an MST there is exactly one path (from the first node up to the shared parent and then down to the other node). And all nodes that are connected in the greater graph, are connected in the MST. Moreover, it is optimal in the number of edges. I don't think so because for a given set of nodes I am only looking for paths that go through all those nodes one time. While a minimum spanning tree will give me a path, it generally won't give me ones that go through all the nodes in the set. Then I misunderstood your problem. The way you explained it it didn't sound like you wanted a single path. Rather you wanted a collection of edges that, together, connected your subgraph with a minimum number of edges. That is an MST. What you describe now, however, sounds like a Hamiltonian path? Which is an NP-complete problem, and a much studied one at that. | ||
Deleted User 3420
24492 Posts
April 05 2018 21:48 GMT
#19052
Then, a node is removed, and you need to find "hamiltonian" paths of length n-1 in the reduced graph. Then, the node is put back in, a different node is removed, and you must find paths of length n-1 for this new graph. We repeat this process some amount of times. Now we have a shitload of different paths of all length n-1. Each time we found new paths, the paths will be different than last time, because the nodes of our graph were different (by one node). However, n-1 nodes were the same, and many edges used are likely to be the same. So my problem is: what is the least amount of edges we can use to be able to form a path of length n-1 from each of our subgraphs? The problem being NP complete isn't as much of a concern because the context in which it is being used is a very sparse graph. I mean obviously it could still be a problem but that's not the point anyways. But like I said this issue isn't really a concern anymore, though I do think it is an interesting and difficult problem (the final step where I try to find a minimum set of edges, not the finding of the paths themselves). | ||
phar
United States1080 Posts
April 06 2018 15:48 GMT
#19053
[ {{ (1,2) ; (2, 4); ... }, { (2,3) ; (2, 4) ; ... {{ ... }} {{ ... }} ] And you just need to minimize the stuff inside - leave at least one set in each list, eliminating all others, where you can only eliminate all sub sub sets that contain a given element all at the same time. That to me doesn't feel like a graph problem once you've distilled it. | ||
raNazUra
United States9 Posts
April 06 2018 16:16 GMT
#19054
On April 07 2018 00:48 phar wrote: Maybe I misread your problem (sorry, skimmed it), but your problem doesn't really need the graph at all? As in you have a list of sets of sets of things: [ {{ (1,2) ; (2, 4); ... }, { (2,3) ; (2, 4) ; ... {{ ... }} {{ ... }} ] And you just need to minimize the stuff inside - leave at least one set in each list, eliminating all others, where you can only eliminate all sub sub sets that contain a given element all at the same time. That to me doesn't feel like a graph problem once you've distilled it. Yeah, this was how I interpreted the description as well. "Given a list of sets of inner sets, select one inner set from each outer set such that the union of all selected sets is minimized." On another note, for people who like doing coding/algorithmic challenges, Google's yearly Codejam is starting up later today. The qualification round is usually pretty trivial, things start getting more fun in rounds 1 and 2. Edit: Re-read the description of travis' problem, and based on that description its definitely MST. Based on the follow-up clarification, I think that the misstatement is describing the original set of paths being collected as 'simple' paths, when they really are supposed to be Hamiltonian paths? Is that accurate? If that's the case, we can add to the above formulation that all inner sets are the same length, on the off chance that's useful in any way. | ||
Deleted User 3420
24492 Posts
April 06 2018 19:28 GMT
#19055
On April 07 2018 00:48 phar wrote: Maybe I misread your problem (sorry, skimmed it), but your problem doesn't really need the graph at all? As in you have a list of sets of sets of things: [ {{ (1,2) ; (2, 4); ... }, { (2,3) ; (2, 4) ; ... {{ ... }} {{ ... }} ] And you just need to minimize the stuff inside - leave at least one set in each list, eliminating all others, where you can only eliminate all sub sub sets that contain a given element all at the same time. That to me doesn't feel like a graph problem once you've distilled it. Yep, it is not a graph problem. I feel like I didn't really frame it as one, though. I was just describing the situation. On April 07 2018 01:16 raNazUra wrote: Show nested quote + On April 07 2018 00:48 phar wrote: Maybe I misread your problem (sorry, skimmed it), but your problem doesn't really need the graph at all? As in you have a list of sets of sets of things: [ {{ (1,2) ; (2, 4); ... }, { (2,3) ; (2, 4) ; ... {{ ... }} {{ ... }} ] And you just need to minimize the stuff inside - leave at least one set in each list, eliminating all others, where you can only eliminate all sub sub sets that contain a given element all at the same time. That to me doesn't feel like a graph problem once you've distilled it. Yeah, this was how I interpreted the description as well. "Given a list of sets of inner sets, select one inner set from each outer set such that the union of all selected sets is minimized." On another note, for people who like doing coding/algorithmic challenges, Google's yearly Codejam is starting up later today. The qualification round is usually pretty trivial, things start getting more fun in rounds 1 and 2. Edit: Re-read the description of travis' problem, and based on that description its definitely MST. Based on the follow-up clarification, I think that the misstatement is describing the original set of paths being collected as 'simple' paths, when they really are supposed to be Hamiltonian paths? Is that accurate? If that's the case, we can add to the above formulation that all inner sets are the same length, on the off chance that's useful in any way. Well, I do say that the simple paths touch every node in the collection. I didn't want to say hamiltonian path because I thought it could be confusing since we are addressing a subgraph of a greater graph. But I suppose I was just more confusing. Maybe I was doomed either way. | ||
raNazUra
United States9 Posts
April 06 2018 19:50 GMT
#19056
On April 07 2018 04:28 travis wrote: Show nested quote + On April 07 2018 00:48 phar wrote: Maybe I misread your problem (sorry, skimmed it), but your problem doesn't really need the graph at all? As in you have a list of sets of sets of things: [ {{ (1,2) ; (2, 4); ... }, { (2,3) ; (2, 4) ; ... {{ ... }} {{ ... }} ] And you just need to minimize the stuff inside - leave at least one set in each list, eliminating all others, where you can only eliminate all sub sub sets that contain a given element all at the same time. That to me doesn't feel like a graph problem once you've distilled it. Yep, it is not a graph problem. I feel like I didn't really frame it as one, though. I was just describing the situation. Show nested quote + On April 07 2018 01:16 raNazUra wrote: On April 07 2018 00:48 phar wrote: Maybe I misread your problem (sorry, skimmed it), but your problem doesn't really need the graph at all? As in you have a list of sets of sets of things: [ {{ (1,2) ; (2, 4); ... }, { (2,3) ; (2, 4) ; ... {{ ... }} {{ ... }} ] And you just need to minimize the stuff inside - leave at least one set in each list, eliminating all others, where you can only eliminate all sub sub sets that contain a given element all at the same time. That to me doesn't feel like a graph problem once you've distilled it. Yeah, this was how I interpreted the description as well. "Given a list of sets of inner sets, select one inner set from each outer set such that the union of all selected sets is minimized." On another note, for people who like doing coding/algorithmic challenges, Google's yearly Codejam is starting up later today. The qualification round is usually pretty trivial, things start getting more fun in rounds 1 and 2. Edit: Re-read the description of travis' problem, and based on that description its definitely MST. Based on the follow-up clarification, I think that the misstatement is describing the original set of paths being collected as 'simple' paths, when they really are supposed to be Hamiltonian paths? Is that accurate? If that's the case, we can add to the above formulation that all inner sets are the same length, on the off chance that's useful in any way. Well, I do say that the simple paths touch every node in the collection. I didn't want to say hamiltonian path because I thought it could be confusing since we are addressing a subgraph of a greater graph. But I suppose I was just more confusing. Maybe I was doomed either way. Yeah, that's fair. It's a bit of a wonky situation. Also, giving the setup is actually useful, since it adds constraints that the simple formulation would otherwise ignore. Like the fact that each set has k elements, and the number of distinct elements that can show up in the sets is k^2, and there are serious constraints on which elements can show up together (can't start or end on the same node as another edge). Sometimes those kinds of things are useful, though I don't immediately see how to either solve this problem nor reduce it to NP-complete either. | ||
WarSame
Canada1950 Posts
April 11 2018 03:55 GMT
#19057
Do you need 1 docker-compose per environment? How do you handle environment changes between containers? When I am developing(say a Flask app) I have a mounted volume to auto update my code. When I am done developing I commit to my own branch("flask-101013033", maybe). QA comes in and verifies that this branch works correctly by pulling the branch, building an image from the branch and making a container from the image. We then move it into integration testing. I merge my code into the integration branch. We then build another image/container for this branch which QA tests for integration. Finally, we move this image into production. Is that a reasonable approach? How do Kubernetes and Docker Swarm come into play? | ||
Manit0u
Poland17046 Posts
April 11 2018 07:53 GMT
#19058
I have a very simple query
For some reason it takes 16-28 seconds to execute. Do you know any potential reasons for that? I've checked most common culprits: 1. Table is not large (10 records) 2. Vacuum and analyze are no older than 2 days Any ideas? Could the problem be the number of concurrent db connections (over 100)? | ||
R1CH
Netherlands10340 Posts
April 11 2018 13:15 GMT
#19059
| ||
Bog
Netherlands49 Posts
April 11 2018 18:31 GMT
#19060
On April 11 2018 16:53 Manit0u wrote: Postgres question: I have a very simple query
For some reason it takes 16-28 seconds to execute. Do you know any potential reasons for that? I've checked most common culprits: 1. Table is not large (10 records) 2. Vacuum and analyze are no older than 2 days Any ideas? Could the problem be the number of concurrent db connections (over 100)? Some ideas; - Check is other transactions aquire locks on your data. Lock monitoring. - Check for any triggers that might be hit on this transaction. SELECT * FROM information_schema.triggers - Check the explain plan for anomalities. EXPLAIN ANALYZE UPDATE "table_name" SET "last_seen_at" = now(), "updated_at" = now() WHERE "table_name"."id" = "uuid";(make sure equality predicate is correctly applied on the primary key. Equality predicates with different types, e.g. x::uuid = y::varchar can sometimes cause unexpected behaviour) - Check your isolation level SELECT current_setting('transaction_isolation');. Concurrent access to data could be severely hindered when your isolation level is unnecessarily high (e.g. 'serializable'). Consider setting the level to 'read committed' if your business logic allows. - When using JDBC, check if your transaction is committed at the earliest moment your business logic allows. Extra care should be taken when defaultAutoCommit=false for your JDBC connection or connection-pool property, then always close the transaction/connection explicitly in your code. | ||
| ||
The PiG Daily
Best Games of SC
Clem vs Rogue
Reynor vs TBD
Dark vs ReBellioN
herO vs TBD
PiGStarcraft520
[ Submit Event ] |
StarCraft 2 StarCraft: Brood War Dota 2 Other Games tarik_tv59604 gofns22234 summit1g10222 FrodaN4900 sgares624 JimRising 506 shahzam421 NuckleDu251 trigger119 NeuroSwarm116 Maynarde107 ViBE41 Mew2King19 Organizations Other Games StarCraft 2 Other Games StarCraft: Brood War StarCraft 2 StarCraft: Brood War
StarCraft 2 • gosughost_ 27 StarCraft: Brood War• practicex 7 • Gussbus • LaughNgamez Trovo • Poblha • aXEnki • Migwel • intothetv • Laughngamez YouTube • Kozan • IndyKCrew Dota 2 League of Legends Other Games |
ESL Open Cup
ESL Open Cup
ESL Open Cup
GSL Code S
ESL Pro Tour
ESL Pro Tour
ESL Pro Tour
ESL Pro Tour
Online Event
ESL Pro Tour
[ Show More ] Hatchery Cup
BSL
ESL Pro Tour
Sparkling Tuna Cup
ESL Pro Tour
BSL
ESL Pro Tour
|
|