Clojure新手实现Hackerrank计数山谷算法超时求助

Hey there! As someone new to Clojure, it's totally normal to carry over imperative habits from languages like Python—but that's exactly what's causing your performance issues here. Let's break down the key problems and why they're slowing your code down:

1. Global State Is Killing Performance #

Your Clojure code uses def to create global variables (running, valley-num) and modifies them inside helper functions (counter, valley-count). In Clojure, def creates global Vars that come with significant overhead:

• Every modification to a global Var involves dynamic binding checks and thread-safety safeguards, which are way slower than modifying local variables (like your Python code's list and num).
• Global state also makes your code impure, which prevents the JVM from optimizing it effectively—JVM loves predictable, side-effect-free code.

In contrast, your Python code uses local variables that live entirely within the function—accessing and modifying these is lightning-fast with almost no overhead.

2. You're Traversing the Input Twice (Unnecessarily) #

Your Clojure code does two full passes over the input string:

1. First with for to generate the heights sequence by calling counter on each character.
2. Then with doseq to pair each character with its height and call valley-count.

Each traversal adds overhead, especially when dealing with large test cases. Your Python code also does two passes, but Python's loop overhead is lower for simple imperative operations, while Clojure's sequence operations work best when you minimize traversals.

3. Imperative Style Doesn't Play to Clojure's Strengths #

Clojure is designed for functional programming—pure functions, immutable data, and using higher-order functions like reduce instead of loops with side effects. Your code relies on do blocks and mutable state, which:

• Forces the JVM to skip optimizations like inlining or loop unrolling (since it can't predict side effects).
• Goes against Clojure's core design, so you're not leveraging the language's built-in optimizations for functional patterns.

A Faster, Functional Alternative #

Here's how you can rewrite the code using Clojure's strengths—one traversal, no global state, pure functions:

(require '[clojure.string :as str])

(defn countingValleys [n s]
  (let [steps (str/split s #"")]
    ;; Use reduce to track both current height and valley count in one pass
    (:valleys (reduce (fn [{:keys [current-height valleys]} step]
                        (let [new-height (if (= step "U")
                                           (inc current-height)
                                           (dec current-height))
                              ;; Increment valley count only if we just climbed back to sea level
                              new-valleys (if (and (= step "U") (= new-height 0))
                                            (inc valleys)
                                            valleys)]
                          {:current-height new-height
                           :valleys new-valleys}))
                      {:current-height 0 :valleys 0} ; Initial state
                      steps))))

This version uses reduce to accumulate state (current height and number of valleys) in a single pass over the input. It's pure, immutable, and the JVM can optimize it much more effectively—you'll see it pass all test cases without timing out.

内容的提问来源于stack exchange，提问作者zengod