The Big Programming Thread - Page 949

Prev 1 947 948 949 950 951 1032 Next

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

Poland4769 Posts

March 01 2018 12:15 GMT

#18961

Exactly, i think it is both resource inefficient and programmer time inefficient. I mean just for checking if filename/path is valid You can just perform some filename/path operation on it and validate basing if it returns error or not. I mean at least for me that would be faster than writing those regex.

tofucake

Hyrule19268 Posts

March 01 2018 13:54 GMT

#18962

if that's all you want, use _splitpath_s?

R1CH

Netherlands10343 Posts

March 01 2018 14:24 GMT

#18963

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.

Manit0u

Poland17871 Posts

March 01 2018 22:54 GMT

#18964

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

Spain18488 Posts

March 01 2018 23:50 GMT

#18965

On March 02 2018 07:54 Manit0u wrote:

Show nested quote +

Try:
Read stuff from file
Catch:
Raise userisanidioterror

Should be fine.

Manit0u

Poland17871 Posts

March 02 2018 16:15 GMT

#18966

On March 02 2018 08:50 Acrofales wrote:

Show nested quote +

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

March 04 2018 17:58 GMT

#18967

Here's a challenge question for you guys:

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

Germany3943 Posts

March 04 2018 18:21 GMT

#18968

Uhm....

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)


i = 1
j = 1
while (i<=size(K,1) && j<=size(L,1))
  if K[i]==L[j]
    return true
  end
  if K[i]<L[j]
    i+=1
  else
    j+=1
  end
end
return false

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

March 04 2018 18:39 GMT

#18969

I use this for solving TSP so I don't really care about order. In fact, I can reduce my search space by throwing out suboptimal paths much faster if they are represented in a way that isn't ordered. As far as scaling goes, I understand that bit sequences can quickly get incredibly huge, but I still haven't been convinced that representing pathways with a series of smaller values saves much memory. as the paths get large.

mahrgell

Germany3943 Posts

March 04 2018 18:50 GMT

#18970

I was just trying to solve your issue about "how to quickly find out, if the pathes have common nodes".

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

March 04 2018 19:03 GMT

#18971

Yeah I am sorry, the question is hard for me to formulate.

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

Germany3943 Posts

March 04 2018 21:45 GMT

#18972

hm?
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

March 04 2018 21:58 GMT

#18973

The data structure you want to use is called UnionFind. Its hyper log fast, so practically constant time check to see if two nodes are connected.

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

March 04 2018 22:58 GMT

#18974

mahrgell, that's actually exactly what I do right now

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

March 05 2018 02:28 GMT

#18975

A classic case for union find is percolation. Basically, given two nodes in a graph, find if two nodes are connected in constant time. The data structure wont tell you the exact path, but only if there is a path (connected components). If you know these two nodes are connected and you need a path, you can use BFS or get to the optimum path in O(|V| + |E|). Union Find can be implement in ~10 lines of code.

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

Poland4769 Posts

March 05 2018 10:37 GMT

#18976

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

ZerOCoolSC2

9077 Posts

March 05 2018 16:26 GMT

#18977

Is it a dashboard feature or navigation feature? Is that covered by NDA?

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

March 05 2018 17:11 GMT

#18978

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

Poland4769 Posts

March 05 2018 17:48 GMT

#18979

Well Windows is ~50mln, Linux kernel ~15mln.
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

March 06 2018 04:57 GMT

#18980

On March 06 2018 02:11 spinesheath wrote:

Show nested quote +

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.

Prev 1 947 948 949 950 951 1032 Next

Please or register to reply.

The Big Programming Thread - Page 949

Completed

Ongoing

Upcoming