The Big Programming Thread - Page 949
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. | ||
Silvanel
Poland4601 Posts
| ||
tofucake
Hyrule18767 Posts
| ||
R1CH
Netherlands10340 Posts
| ||
Manit0u
Poland17046 Posts
On March 01 2018 23:24 R1CH wrote: I would agree, the best test to see if something is valid is to try and use it. Trying to validate something that the OS already validates is a bad idea in the long run, eg if Windows begins allowing reserved device names then the regex is outdated, similarly the regex for a valid IP address seems to ignore that IPv6 exists. The problem is that the client has to transfer files between OS's and they do really stupid things with filenames. I'm not a fan of validating it like that either but that's the demand we have to meet. | ||
Acrofales
Spain17185 Posts
On March 02 2018 07:54 Manit0u wrote: The problem is that the client has to transfer files between OS's and they do really stupid things with filenames. I'm not a fan of validating it like that either but that's the demand we have to meet. Try: Read stuff from file Catch: Raise userisanidioterror Should be fine. | ||
Manit0u
Poland17046 Posts
On March 02 2018 08:50 Acrofales wrote: Try: Read stuff from file Catch: Raise userisanidioterror Should be fine. Well, I can't do that. The server is on Linux and it allows files that Windows won't allow Also, I'm never dealing with files directly, we're sending them to S3. | ||
Deleted User 3420
24492 Posts
At the moment, my favorite way to implement graph BFS if by representing paths with binary sequences, and then checking that the intersection between two paths is 0, and therefore they do not contain common nodes. What I have been doing is mapping a key of [(front node)] to a list of (binary sequence, back node) where the binary sequences represent the path between back and front. Doing this I can easily check for overlap in the paths, and look up where two subpaths would connect by (front node) While this is pretty damn good, I feel it could be better. I don't like having to take a potentially long list of binary sequences and do the intersection between each pair of them. I feel like there must be some sort of structure I could use other than a list, where when I connect two binary sequences subpaths, I could place them into my structure such that groups of sequences with no intersection would be related and easily traversable. Something like an adjacency list or a tree, based on intersections. Where, from any given sequence, I can traverse the structure in a certain way so that I only would iterate over other sequences that have an intersection of zero with my first sequence. I don't even really know how to explain what it is I want very well... but hopefully you guys understand. Anyways I have to guess, such a structure isn't really feasible. But maybe it is. | ||
mahrgell
Germany3854 Posts
Assuming each node having an ID, why not just store a sorted list of the IDs that are part of the path. Then you can easily compare the lists for shared IDs. + Show Spoiler + If you dont have some quick and available comparison between those lists and you are handwriting that comparison, it would probably be something like the following: (for lists L and K, julia code, but should be all be easily understood)
For small numbers of nodes, having bitsets and using AND between the bitsets is faster, but this has obvious scaling issues. | ||
Deleted User 3420
24492 Posts
| ||
mahrgell
Germany3854 Posts
For this purpose, my described suggestion should compare this rather quick. But sure, if you assume that bitsets are the most efficient way store all the nodes of a path, then simply using "iszero(L & K)" is the fastest comparison. But then I don't understand the question. | ||
Deleted User 3420
24492 Posts
The idea is that I traverse the graph in "rounds" (typical BFS style). But, lets say that instead of traversing by adding one edge at a time to my subpaths of size k, I wanted to traverse by adding all the other explored subpaths of size k, to each subpath of size k. So like, instead of adding edge (0,5) to 3-7-9-4-0, I would be adding subpaths such as 0-5-11-12-1 to 3-7-9-4-0. And in theory this sounds pretty efficient, but what ends up happening is that the sheer amount of intersections I have to calculate is not worth it. I end up having a large list of bit sequences, and then for every list I have to do [k choose 2], and sometimes its super huge. So my thought is, what if the subpaths weren't organized with just lists. What if there was a structure (think heap, or tree, or something) - where I could insert my subpaths, and as they were inserted they could be efficiently organized so that I could go to any sequence in the structure, and easily traverse only the other sequences that had intersection 0. Does that make it a little more clear what I am dreaming up? | ||
mahrgell
Germany3854 Posts
If you aren't shying away from using bitsets and I understood your problem correctly, then I would do it the following: Have a struct of path - howeveryouarestoringthem bs - bitset with as many bits as there are nodes, with all nodes that are part of the path flagged as 1, rest 0. Now you can store them in a map, containing lists of those structs... as mapkey you use the first node of a path, and the list contains all pathes (aka the struct from above) starting with that node. Now if you pick a path A, you can simply access the map, getting all the pathes B you could attach to your path A. Next you can check "tbs=A.bs & B.bs", remove the shared node from tbs ("tbs.reset(sharednodeID)", and then tbs.any() will tell you if those pathes somehow cross except for that one node. If you get a new path C, you append your pathes however you do, and "C.bs = A.bs | B.bs" and you have the new struct for your path. | ||
Neshapotamus
United States163 Posts
You can use this data structure to see if two nodes have a path between them using the find function. If they don't, you can join them using the union function. I think this is what you want. Only downside to UF is that you cant unjoin nodes. | ||
Deleted User 3420
24492 Posts
The issue is that for larger graphs, as I start to near (n/2)-length subpaths, the list for each start node can be quite long. And you end up having to do [A.bs & (1 million other bitsets)]. And you have to do that for every bitset in the list. And then you have to do that for every start node. So I was wanting to take it to another level, where I could structure it so that paths were organized by disjunction (or union). Neshapotamus: I had seen this before in my research and I remember being very interested but then I must have gotten distracted or something turned me away. But now, it does look like what I want. To use bit sequences I would need to learn the algorithm really well so that I can write my own version or modify one, though. If I don't use bit sequences then I may need to find a way to serialize it, which is something I know nothing about. But it sounds like something I should really look into. | ||
Neshapotamus
United States163 Posts
You can find everything you need to know about the data structure here: (Just watch the first video) http://www.cs.princeton.edu/courses/archive/spring18/cos226/lectures.php | ||
Silvanel
Poland4601 Posts
50+ millions lines of code. Edit: Intially i wanted to write more but then realized i actualy cant so in the end post became short and empty | ||
ZerOCoolSC2
8701 Posts
So, I'm getting back into programming after 12 years of being MIA. I started with C++ after messing with CSS and HTML and JS back in the good ole days. I'm reading up on C# and was wondering if anyone had any suggestions. I'm using Tutorials Teacher C# at the moment to get a quick overview. I find that I understand it, but I'm just trying to get a better understanding of the syntax. I'm sure I could get more from a MSDN or github search, in regards to code and information that I'm seeking. Just wanted to get some other opinions. Thanks in advance. I'm using Unity 3D, Visual Studio, and probably notepad when I'm more comfortable. | ||
spinesheath
Germany8679 Posts
On March 05 2018 19:37 Silvanel wrote: So we have succesfully delivered software to customer. You can see it in new Mercedes A-classes from May/June. 50+ millions lines of code. Edit: Intially i wanted to write more but then realized i actualy cant so in the end post became short and empty How the codebase gets as large as that is still a mystery to me. | ||
Silvanel
Poland4601 Posts
Modern car in reality consist of several different computers some of those run more than one OS at the same time. So its not that strange, but it is still a gigantic enterprise to build one, especially from scratch. We deliver a whole product (complete system and hardware) to customer (Daimler) but we also have our own suppliers delivering various parts of system like Navigation etc. | ||
phar
United States1080 Posts
On March 06 2018 02:11 spinesheath wrote: How the codebase gets as large as that is still a mystery to me. Not too surprising at big companies. That's why there is hopefully market for static analysis tooling on O(100m) LoC repositories like I was talking about week or so back... when code gets that big you start needing different tooling to handle it than you're otherwise used to. | ||
| ||