Hello,
I want to write a program that determines whether a sentence is a palindrome or not. I wrote the following program and it works, but I want to know if this piece of code is flawed from a programming science perspective:
function palindrome(str)
ch = ""
temp = ""
str = lowercase(str)
for i = 1 : length(str)
if isletter(str[i])
ch *= str[i]
end
end
for i = length(ch) : -1 : 1
temp *= ch[i]
end
if ch == temp
return true
else
return false
end
end
function main()
print("Please enter a string: ")
str = readline()
if palindrome(str)
println(str," is a palindrome.")
else
println(str," is not a palindrome.")
end
end
main()
Incrementally building a string in this way is not recommended. A pre-allocated character array will perform better. But unless there’s a good reason not to, just use @g-gundam’s one-liner solutions.
Or don’t create a new String at all, and instead just compare (valid) characters in the input str by moving from front to back and back to front simultaneously
This depends on what your goals are. It is neither the most efficient implementation (as you create multiple extra Strings (in a suboptimal way, cf. @greatpet 's reply)), nor the shortest implementation (cf. @g-gundam, and even if you like to iterate explicitly, you could also just use return ch == temp, for example). I would also argue that “a12a” is not a palindrome.
But most often you don’t really need the fastest or shortest implementation. In this example, the IO time will likely dwarf the execution time for palindrome. In any case, the user will not notice the difference between 1 ns and 1 ms.
Hello,
Thank you so much for your reply.
I’m a newbie and learning Julia. I haven’t learned arrays yet. I have currently learned numbers, for and while loops, functions, and characters and strings in Julia.
With my current knowledge, is this program well written?
Is there a specific reason why you think your code might be “flawed”? It seems fine enough to me.
If you don’t want to use functions like (Iterators.)filter or reverse, I’m personally a bit more partial to something like
function is_palindrome(str)
i = 1 # moves front to back
j = length(str) # moves back to front
while i <= length(str) && j >= 1
# Move i forward to the first valid next character
if !isletter(str[i])
i += 1
continue
end
# Move j backward to the first valid previous character
if !isletter(str[j])
j -= 1
continue
end
lowercase(str[i]) == lowercase(str[j]) || return false
i += 1
j -= 1
end
return true
end
the interpretation of which might also be a good exercise in control flow (you could make it a bit easier by using nested while loops, potentially moved to a different function). I would also just leave out the isletter checks and lowercase conversion, but that depends on your definition of palindrome.
@assume_effects :foldable @inline function codeunit(s::String, i::Int)
@boundscheck checkbounds(s, i)
b = GC.@preserve s unsafe_load(pointer(s, i))
return b
end
@propagate_inbounds function getindex(s::String, i::Int)
b = codeunit(s, i)
u = UInt32(b) << 24
between(b, 0x80, 0xf7) || return reinterpret(Char, u)
return getindex_continued(s, i, u)
end
function getindex_continued(s::String, i::Int, u::UInt32)
if u < 0xc0000000
# called from `getindex` which checks bounds
@inbounds isvalid(s, i) && @goto ret
string_index_err(s, i)
end
n = ncodeunits(s)
(i += 1) > n && @goto ret
@inbounds b = codeunit(s, i) # cont byte 1
b & 0xc0 == 0x80 || @goto ret
u |= UInt32(b) << 16
((i += 1) > n) | (u < 0xe0000000) && @goto ret
@inbounds b = codeunit(s, i) # cont byte 2
b & 0xc0 == 0x80 || @goto ret
u |= UInt32(b) << 8
((i += 1) > n) | (u < 0xf0000000) && @goto ret
@inbounds b = codeunit(s, i) # cont byte 3
b & 0xc0 == 0x80 || @goto ret
u |= UInt32(b)
@label ret
return reinterpret(Char, u)
end
In particular, for ASCII characters getindex_continued will never be called.
For non-ASCII strings the above is_palindrome and original palindrome implementations would then fail (and are hence indeed flawed to some extent), while reverse would work. As a compromise you could change the indices i and j into Chars obtained from iterating over str and Iterators.reverse(str) via iterate.
You’re conpletely right, I totally forgot that Julia guaranteed constant time string indexing. It’s just that the getindex result may not be an actual character.
Hello,
Thanks again.
That’s why I asked because I’m a novice and I want to know if I’m on the right track or not?
How can I calculate the execution time of the program?
I’d say you’re on the right track if you don’t want to use too many of the built-in features of the language. But as highlighted by @greatpet and @stevengj, Unicode strings (using characters from outside the Latin alphabet, requiring potentially more than 1 byte for a given Char) will lead to complications and we cannot just use simple incremental indexing (for i = 1:length(str) or i += 1), though for i = eachindex(str) is fine. As long as you intend the user to only supply simple ASCII strings (which is mostly sufficient for the English language), you don’t have to worry too much about that though, but it’s still good to keep in mind (and document).
You could look into theoretical computational complexity (the constant time and quadratic time complexity mentioned above). But you could also just measure the execution time, e.g. via BenchmarkTools.jl’s @btime and @benchmark:
using BenchmarkTools
using Random # for randstring to generate a random String
function palindrome1(str) # Made Unicode-proof
ch = ""
temp = ""
str = lowercase(str)
i = 1 # Will be a byte-level index
while i <= sizeof(str) # sizeof returns the byte-length
if isletter(str[i])
ch *= str[i]
end
i = nextind(str, i)
end
i = sizeof(ch) + 1 # Beyond the last byte (which might or might not already correspond to a full Char)
i = prevind(ch, i) # Now the start of the last Char in ch
while i >= 1
temp *= ch[i]
i = prevind(ch, i)
end
return ch == temp
end
palindrome2(str) = let ch = filter(isletter, lowercase.(str)) # (Already worked fine)
reverse(ch) == ch
end
function palindrome3(str) # Also made Unicode-proof
i = 1 # moves front to back
j = sizeof(str) + 1; j = prevind(str, j) # moves back to front
while i <= j # (Note: Changed to exploit symmetry)
# Move i forward to the first valid next character
if !isletter(str[i])
i = nextind(str, i)
continue
end
# Move j backward to the first valid previous character
if !isletter(str[j])
j = prevind(str, j)
continue
end
lowercase(str[i]) == lowercase(str[j]) || return false
i = nextind(str, i)
j = prevind(str, j)
end
return true
end
# Below we return the minimal (best) execution time over a number of runs (determined automatically)
# for checking that a random string (not the same one each time) of length 1000 is a palindrome.
# We do not include the creation of the string to test in the timing.
# (By default randstring only uses standard Latin letters and digits, hence only ASCII character)
# Very likely non-palindromes:
@btime palindrome1(s) setup=(s = randstr(1000)); # 97.800 μs (1590 allocations: 673.77 KiB)
@btime palindrome2(s) setup=(s = randstr(1000)); # 11.800 μs (7 allocations: 6.30 KiB)
@btime palindrome2(s) setup=(s = randstr(1000)); # 19.358 ns (0 allocations: 0 bytes)
# (We immediately return False after comparing the first and last character.)
# Palindromes:
@btime palindrome1(s) setup=(s = randstr(500); s *= reverse(s)); # 96.200 μs (1556 allocations: 646.67 KiB)
@btime palindrome2(s) setup=(s = randstr(500); s *= reverse(s)); # 11.700 μs (7 allocations: 6.30 KiB)
@btime palindrome2(s) setup=(s = randstr(500); s *= reverse(s)); # 10.900 μs (0 allocations: 0 bytes)
For interactive usage 100 µs is negligible, so we really don’t have to worry much about computational efficiency here.
No, that should be the same. For some reason (I guess confusion between byte- and Char-indexing) I just didn’t think of lastindex, which would be better in every way.
help?> prevind
search: prevind
prevind(str::AbstractString, i::Integer, n::Integer=1) -> Int
• Case n == 1
(...) If i is equal to ncodeunits(str)+1 return lastindex(str). Otherwise throw BoundsError.
(...)
What I found in learning Julia this year is that the same style of imperative/procedural coding in C carries over easily, and “duck typing” like Python is well tolerated.
But I also learned two important aspects of Julia that reveal its power.
The first is the option to strongly type arguments to functions, including the ability to define specific types to implement data structures that can allow complex data to be packaged in a way that minimizes the manual operations need to be done to analyze your data.
The second is arrays, indexing over them and “broadcasting” with the . operator, which applies a function to each element. What can be naively done with a multiplicity of intermediate objects can be wrapped in a function and handled as a unit.
Keep an eye out for those as you continue learning.
