/dpt/ - Daily Programming Thread

What are you working on, Sup Forums?

Previous thread:

Other urls found in this thread:

stackoverflow.com/questions/23705233/how-to-speed-up-a-algorithm-at-large-spatial-scales
youtu.be/fHNmRkzxHWs?t=505
twitter.com/AnonBabble

too early you fucking retard sage

What is this all powerful sshnuke and where can I get one?

third for Forth

Learning Golang.

fuck off. you just wanted to start a thread with your animu OP

It's never late to start an appropriate thread

posting threads early just causes thread war cancer

1999
hope your time machine works

no one is going to reply to that anymore since those last posts will probably be ignored.
only if you make a fuzz of it

>no one is going to reply to that anymore since those last posts will probably be ignored.
You wish :^)

What's wrong with my A* implementation? I feel it's too slow for a 128x128 grid (north, east, west, south neighbors). It's running at ~15ms per search.
inb4 >java

private List aStar(TilePosition source, TilePosition dest) {
Set visited = Sets.newHashSet();
Map stepWeight = Maps.newHashMap();
stepWeight.put(source, 0);
Map heuristicWeight = Maps.newHashMap();
heuristicWeight.put(source, heuristic(source, dest));
Queue queue = createPriorityQueue(heuristicWeight);
queue.add(source);
MutableGraph tree = GraphBuilder.directed().allowsSelfLoops(false).build();

int stepSize = 1;
while (!queue.isEmpty()) {
TilePosition current = queue.poll();
if (current.equals(dest)) {
return createPath(tree, source, current);
}
visited.add(current);
for (TilePosition child : neighbors(current)) {
if (visited.contains(child)) {
continue;
}
int weight = stepWeight.getOrDefault(current, Integer.MAX_VALUE) + stepSize;
if (!queue.contains(child)) {
queue.add(child);
} else if (weight >= stepWeight.get(child)) {
continue;
}
tree.putEdge(current, child);
stepWeight.put(child, weight);
heuristicWeight.put(child, stepWeight.get(child) + heuristic(child, dest));
}
}
return null;
}

you're doing a lot of initialization on each method call, if you need it to be as fast as possible you should probably reuse objects

I did a dirty profiling and 99% of the runtime is in the while loop

ok well maybe this can help you

stackoverflow.com/questions/23705233/how-to-speed-up-a-algorithm-at-large-spatial-scales

@58282724
it's in java

Yeah, I'm actually reading that now and other related articles.

The heuristic by the way is a simple line distance function.

Waiting for an anime thread.

so close user

where do i go to learn penetration testing?

create your own

i went to your mom

see

>set
>map
Well I'd say your primary issue is that you're taking major performance hits from your iteration.
I'm not a java expert but if these hash-based structures work like I'd normally expect them to you're waiting on memory a lot.
Aim to find structures that work closer to flat arrays and ideally that accesses your data in a cacheline efficient way. But just the first step would let your CPU do wonders.
>java
youtu.be/fHNmRkzxHWs?t=505
>java is faster
It's true. Even the Cpp committee admits it!

he he